[백준] (Swift) 1929번 - 소수찾기 (또 등장한 에라토스테네스의 체)

아직도 소수랑 전쟁중! 역시나 시간초과로 고생중이다. 구현하는건 쉽지만, 이젠 그 이상의 단계를 스스로 파헤쳐보고 깨닫기 위해 노력해야한다. 참 어렵군,,

🟠 문제

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

1929번: 소수 구하기

🟠 첫번째 풀이 - 시간초과

private func solution() {
    let nm = readLine()!.split(separator: " ").map{ Int($0)! }
    for i in nm[0]...nm[1]{
        var flag = false
        for j in 2..<i {
            if i % j == 0 {
                flag = true
            }
        }
        if !flag {
            print(i)
        }
    }
}

solution()

2부터 i까지 모두 for문을 돌렸다. 여기서 내가 이전에 풀었던 문제와 달리, 보지 못한 조건이 있었다. 바로,, 자연수 M과 N 은 1000000까지,,,, 주어진다는 사실... 이것때문에 시간초과가 나지 않았을까? 2초 제한이 굉장히 큰 줄 알았는데, 지난번 문제와 달리 자연수의 범위가 훨씬 커졌기 때문에 결코 긴 시간은 아니었나보다.
(대체 백준에서 이 '길다', '짧다'의 판단은 어떻게 하는걸까?,, 이제야 대충 시간복잡도의 빅O표기법에 대해서는 익혔는데ㅠㅠ,, )

🙋🏻‍♀️ 시간을 재봤다.

이전 포스팅에서 실행속도 관련해서 블로그에 질문을 남겼었다. 감사하게도, iOS 검색하다보면 많이 나오는,, 정주님께서 답변을 주셨다. 백준은 실행속도 측정이 정확하지 않기 때문에 직접 해봐야한다고 하셨다. 😇 정주님,,, 천사,,,,

그래서 앞으로는 직접 실행속도를 측정해보려고 한다!! 

(측정해보니,,) 말도안돼,, i 를 거의 최대숫자 990000으로 주고 돌려보았다. 비교를 위해서, 지난번에 풀었던 문제와 같이 '제곱근'을 활용한 방법과 함께 비교해보았다. 끝나지 않는다.. xcode..이제멈춰줘 이 방법말고 다른 방법을 시도해봐야겠다..

import Foundation

public func progressTime(_ closure: () -> ()) -> TimeInterval {
    let start = CFAbsoluteTimeGetCurrent()
    closure()
    let diff = CFAbsoluteTimeGetCurrent() - start
    return (diff)
}

private func solution() {
    let nm = readLine()!.split(separator: " ").map{ Int($0)! }
    for i in nm[0]...nm[1]{
        var flag = false
        for j in 2..<i {
            if i % j == 0 {
                flag = true
            }
        }
        if !flag {
//            print(i)
        }
    }
}

private func solution2() {
    let nm = readLine()!.split(separator: " ").map{ Int($0)! }
    for i in nm[0]...nm[1]{
        var flag = false
        for j in 2..<Int(sqrt(Double(i))) + 1 {
            if i % j == 0 {
                flag = true
            }
        }
        if !flag {
//            print(i)
        }
    }
}

print(progressTime {
    solution()
})

print(progressTime {
    solution2()
})

끝나지 않는다!!!

🟠 두번째 풀이 - 에라토스테네스의 체 방법으로 풀기 - 맞았습니다!

직접 xcode에서 연산을 해보니 첫번째 코드에서 잘못된 부분을 찾을 수 있었다. nm[0] 부터 nm[1]까지 모든 수에 대해서 각각 한번씩 모두 소수 판별을 거친다는 점이 잘못됐다. 만약, nm이 가장 넓은 범위인, 1부터 100만까지 간다고 쳐보자. 그럼 백만번의 소수 판별이 이루어져야하는 것이다. 이 연산을 최소화하는 것이 가장 효율적인 방법일 것이다.

이전 풀이에서 익혔던, 에라토스테네스의 체 방식을 이용해보자. 100만까지 모든 수에 대한 소수 판별을 미리 해둔 뒤, 입력받은 수에 대해서 소수인지 아닌지에 대한 여부만 판단해서 바로 출력해주자.

이 방법은 실제 실행속도를 측정해보니, 적은 범위에서는 실행속도의 차이가 나지 않았지만 역시 범위가 커졌을때 효율적인 것 같았다!! 

private func solution3() {
    let nm = readLine()!.split(separator: " ").map{ Int($0)! }
    var isprimenum = Array(repeating: true, count: 1000001)
    isprimenum[1] = false
    for i in 2..<1000001 {
        if isprimenum[i] == false {
            continue
        }

        for j in stride(from: i+i, through: 1000000, by: i) {
            isprimenum[j] = false
        }
    }

    for k in nm[0]...nm[1] {
        if isprimenum[k] == true {
            print(k)
        }
    }
}

solution3()

짜잔 ~! 맞았다. 아, 왜 첫시도는 틀렸나면, 1을 처리해주지 않았기 때문~ 😉 기억하세요 여러분 1은 소수가 아닙니다!