[백준] (Swift) 1978번 - 소수찾기 (feat. 제곱근, 에라토스테네스의 체) 질문있습니다,,, 흠

기존 풀이 방식 말고, 다른 풀이 방식 두 가지를 더 담고 있습니다. 끝까지 읽어주세용!

 

🟠 문제

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

🟠 나의 풀이

2부터 i-1까지 돌면서 나머지가 0으로 떨어지는 수가 있으면 flag를 false로 바꿔주었다.

 

🟠 정답코드

private func solution() -> Int {
    let n = Int(readLine()!)!
    let arr = readLine()!.split(separator: " ").map { Int($0)! }
    var answer = [Int]()

    for i in arr {
        var flag = true
        if i == 1 {
            continue
        }
        for j in 2..<i {
            if i % j == 0 {
                flag = false
            }
        }
        if flag {
            answer.append(i)
        }
    }

    return answer.count
}

print(solution())

 

🔖 여기서 잠깐, 

 나는 사실 이 풀이가 시간초과가 날 줄 알고 돌렸는데, 시간초과가 나지 않았다. 그이유는 주어지는 수들이 1000이하이기 때문! 만약 100000까지 주어질 수 있다면, 2부터 i-1까지 모든 수를 순회하는 것은, 굉장한 시간이 소요될 것이다. 그럼 이것을 줄이기 위해서는 어떻게할까?

💬 제곱근까지 살펴보기

10을 예시로 들어보자.

내가 풀이한 방법은, 2,3,4,5,6,7,8,9까지 모두 10으로 나눠보고, 결정하는 풀이로 작성했다. 현재 10은 2로 나누어떨어지기 때문에 루프가 한번만 돌고 끝나지만, 만약 그렇지 않은 경우는 최대 8번의 루프가 돈다는 말이다. 이 루프 횟수를 최대한 줄이는 방식으로 진행이 가능하다. 

10의 약수는 1,2,5,10 이렇게 네개이다. 약수의 특징을 보면, 대칭을 이룬다 .즉

1 x 10 
2 x 5
5 x 2
10 x 1

이 경우를 보면, 2 까지만 판별해봅면, 이 수가 소수인지 아닌지 알 수 있다. 이 성질을 이용할 것이다.
10에 루트를 씌워서 제곱근을 구해보자. 그리고 이 제곱근은 애매한 소수로 나오기 때문에, +1 해준 수까지만 구해보자.

private func solution() -> Int {
    let n = Int(readLine()!)!
    let arr = readLine()!.split(separator: " ").map { Int($0)! }
    var answer = [Int]()

    for i in arr {
        var flag = true
        if i == 1 {
            continue
        }
        for j in 2..<Int(sqrt(Double(i)))+1 {
            if i % j == 0 {
                flag = false
            }
        }
        if flag {
            answer.append(i)
        }
    }

    return answer.count
}

for문을 보면, 2부터 i까지 순회를 돌았던 것이, Int(squart(Double(i)))+1 로 바꿔줬다. (sqrt는 double만 취급하기 때문에, i를 double로 바꿔주고, 다시 int로 바꿔주는 과정이 필요하다.)

이렇게 하게 되면 기존에 돌던 루프가 반토막이 나서 시간이 조금 덜 소요되겠지!

 

💬 에라토스테네스의 체

이것을 이용하면 조금 더 효율적으로 소수를 구할 수 있다고 한다. 어머머,,, 이건 또 뭐람,,찾아보니 생각보다 간단하다. 방법은 아래와 같다.

1. 먼저 배열에 판별해야하는 수들을 다 넣어준다.
2. 2부터 자신의 배수가되는 숫자들을 모두 지워준다. (자신은 제외)
3. 3부터 자시느이 배수가 되는 숫자들을 지워준다. (자신은 제외) 
... 반복

여기서 만약 이미 제외된 수라면, 건너뛰어준다.

간단하다! 2부터 순회하면서 그 수의 배수들은 지워주는 것이다. 2부터 시작하게 될텐데, 자기 자신은 제외하고 지워주게 되니까, 제일 작은 소수 2는 그대로 남게된다. 이 과정을 반복하게 되면, 약수를 가지지 않는 수만 남을 것이다!

private func solution() -> Int {
    let n = Int(readLine()!)!
    let arr = readLine()!.split(separator: " ").map { Int($0)! }
    var answer = [Int]()
    var visited = Array(repeating: false, count: 1001)
    visited[0] = true
    visited[1] = true
    // 1000까지 미리 소수 판별
    for i in 2...1000 {
        if visited[i] == true {
            continue
        }

        for j in stride(from: i+i, through: 1000, by: i) {
            visited[j] = true
        }
    }

    // flase 이면 출력
    for k in arr {
        if visited[k] == false {
            answer.append(k)
        }
    }

    return answer.count
}

print(solution())

 

근데,,놀랍게도 에라토스테네스의 체와 일반 2부터 i까지 모두 순회했을때랑 메모리랑 시간차이가 나지 않았다. ㅋㅋㅋㅋ

 

그럼 제곱근을 이용했을때는?

오.. 이게 메모리랑 시간이 더걸리는데..? 뭐냐..뭐냐...

 

🙋🏻‍♀️ 지나가는 고수님들께 질문

1. 제곱근을 이용해서 시간복잡도를 줄였다고 생각했는데, 시간과 메모리가 더 늘어난 이유
2. 에라토스테네스의 체를 이용하는 것이 효율적인 소수를 구하는 알고리즘이라고 했는데, 왜,,, 전체를 순회하는 것과 시간복잡도, 메모리가 동일하게 드는지,,,

궁금합니다.. 혹시 N과 수의 범위가 너무 작아서? 동일하게 나오는것인가요.? 흠,,