[Swift] 프로그래머스 소수 찾기(lv. 1)

[Swift] 프로그래머스 소수 찾기(lv. 1)

 

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

2. 접근

소수를 판별하는 것이 아니라 주어진 수보다 작은 자연수 중에서 소수가 몇 개 인지를 구하는 문제이다.

n개의 원소를 가지는 배열을 만들어서 차례로 올라가는 수를 numArray에 세팅해준다.

 

그런 다음 numArray를 순회하는데, 여기서 중요한 것은 전부를 순회하게 되면 시간초과가 난다는 점이다.

n이 100만이기 때문에 nlogn 이상의 시간복잡도는 사용하지 못한다.

 

그렇기에 이중 반복문을 사용하는데, 내부 반복문은 조금 특이하게 구성한다.

i + i 부터 n 까지 순회를 하고, 그 다음 인덱스를 i 만큼 더해서 순회를 하는 구조를 만들었다.

 

만약 n이 10으로 주어졌다면 다음과 같은 반복을 돌 것이다.

i = 2 이면

numArray[2] != 0 이기에 그 다음 내부 반복문으로 들어간다.

그러면 4부터 10까지 2를 더해가면서 그 인덱스 자리에 있는 원소를 0으로 만들어준다.

여기서 0은 '소수가 아니라는 뜻' 이다. 2의 배수이기 때문에 특별히 소수가 아니라는 것을 보장할 수 있다.

그러면 numArray의 내부는 한 번을 실행하고 나면 다음과 같은 상태가 된다.

 

numArray = [0, 1, 2, 3, 0, 5, 0, 7, 0, 9, 0]

 

이렇게 되면, 0으로 써진 곳에서는 내부 반복문으로 들어가지 않고 그 다음 수로 반복문을 돌러 갈 것이다.

그러면 이중 반복문을 쓴다고 해서 그대로 n 제곱의 시간복잡도가 생기지 않고 O(NloglogN) 정도로 시간 복잡도를 줄일 수 있다.

 

모든 반복을 끝내고 나면 내부에 0이 아닌 수들은 모두 소수가 아닌 수이다.

 

낮은 수들은 '소수'임을 가정하고 들어가는 알고리즘이다. 2는 소수이기 때문에 이 이상의 배수들은 모두 소수가 아니고, 그 다음 숫자인 3도 소수이며 배수들은 소수가 아니다. 그렇다면 4는? 2가 소수였기 때문에 제외되었다. 그 다음 5는 제외된 적이 없기 때문에 또 그 배수의 숫자들을 제외해주면 된다.

 

쉽게 이야기 하여 소수가 아닌 수를 제거하는 과정을 여러 번 거쳤는데도 남아있는 수들은 '소수'라는 것이다.

 

이 알고리즘은 '에라토스테네스의 체'를 활용한 것이다. 이 알고리즘을 활용하여 코드로 구현한 것에 불과하다.

조금 더 자세하게 알고 싶으면 이 부분을 조금 더 알아보면 좋을 것이다. 

 

 

3. 코드

func solution(_ n:Int) -> Int {
    var numArray = [Int](repeating: 0, count: n + 1)
    for i in 2 ... n {
        numArray[i] = i
    }

    for i in 2 ... n {
        if numArray[i] == 0 {
            continue
        }
        for j in stride(from: i + i, through: n, by: i) {
            numArray[j] = 0
        }
    }

    return numArray.filter({ $0 != 0 }).count
}