[백준] (Swift) 6588번 - 골드바흐의 추측

 

아아 아직도 시간초과와 싸우는중,, 지금은 '시간초과 날거같은데..'하면서 코드를 갈겨 쓰고있다. 하지만,,,,,,,, 애초에 문제 풀이 시작할때부터 시간초과에 대한 생각을하고 알고리즘을 짜는게....맞다..백번 맞다. 내가 잘못하고 있는것이다 ㅠㅠ
하나씩 해결해나가면서 시간초과의 원인을 찾아 나서면, 점차,, 익숙해지겠지..?

 

🟠 문제

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

6588번: 골드바흐의 추측

 

🟠 첫번째 풀이 - 역시나 시간초과

private func solution() {
    let isprime = primeNumArr()
    var primeNum = [Int]()
    for i in 1..<isprime.count {
        if isprime[i] == true {
            primeNum.append(i)
        }
    }

    for _ in 0..<100000 {
        var flag = false
        let n = Int(readLine()!)!

        if n == 0 {
            break
        } else {
            flag = true
            for num in primeNum {
                if primeNum.contains(n - num) {
                    print("\(n) = \(num) + \(n-num)")
                    break
                }
            }
        }
        if !flag {
            print("Goldbach's conjecture is wrong.")
        }
    }
}

private func primeNumArr() -> [Bool] {
    var isprimenum = Array(repeating: true, count: 1000001)
    isprimenum[1] = false
    for i in 1..<1000001 {
        if isprimenum[i] == false {
            continue
        }

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

solution()

나의 첫번째 풀이다. 시간초과가 날거같다! 하면서 풀었다. (.. 그럼.. 풀질말았어야지)
시간복잡도는,,, 이중 포문이 들어가있는만큼 O(N^2)로 예상된다. 어마어마하다... 어느 부분에서  효율을 높일 수 있을까?

 

🟠 두번째 풀이 - 맞았습니다!

음,, 사실 바꿔준건 별로 없다. 그래도 확실히 for루프 돌아가는 시간을 줄였다. 어쨌든, 이중포문을 사용했기 때문에 O(N^2)은 맞지만, 상황에 따라 for 루프가 돌아가는 것을 줄여줬다고 생각하면 된다. 

먼저 isprime == true 인 부분의 index만 뽑아내는 for문을 없앴다. 나는 for 문을 돌려서, 숫자를 빼고 더해야해서 firstIndex를 사용해서 인덱스값을 먼저 추출해줘야한다고 생각했다. 쓸데없는 for문이 한 번 더 들어간셈이다. 그냥, isprime만을 사용해서 T/F만 판별하는 것이 시간적으로도, 코드적으로도 훨씬 효율적이다.

// ❌ 두번째 정답코드에서는 이 부분을 삭제했다.

for i in 1..<isprime.count {
    if isprime[i] == true {
        primeNum.append(i)
    }
}

두번째로 바뀐 부분은 아래와 같다. 이중 포문이 되는 부분을 보면 첫번째 풀이는 어떤 수들을 판별하던 간에, primeNum을 전부 살펴보게 된다. 맞은 두번째 풀이는, 3부터 N까지만 보면서 최대한 보는 for루프 돌아가는 횟수를 줄여줬다. 그리고 if 문을 사용해서 isprime에서 true값을 갖는지 살펴만 줬다. 

// ❌ 첫번째 풀이
for _ in 0..<100000 {
    var flag = false
    let n = Int(readLine()!)!

    if n == 0 {
        break
    } else {
        flag = true
        for num in primeNum {
            if primeNum.contains(n - num) {
                print("\(n) = \(num) + \(n-num)")
                break
            }
        }
    }
    if !flag {
        print("Goldbach's conjecture is wrong.")
    }
}

// ✅ 두번째 풀이
for _ in 0..<100000 {
    var flag = false
    let n = Int(readLine()!)!

    if n == 0 {
        break
    } else {
        for i in 3...n {
            if isprime[i] {
                let diff = n - i
                if isprime[diff] {
                    flag = true
                    print("\(n) = \(i) + \(diff)")
                    break
                }
            }
        }
    }

    if !flag {
        print("Goldbach's conjecture is wrong.")
    }
}

 

🟠 최종 정답코드

import Foundation

private func solution() {
    let isprime = primeNumArr()

    for _ in 0..<100000 {
        var flag = false
        let n = Int(readLine()!)!

        if n == 0 {
            break
        } else {
            for i in 3...n {
                if isprime[i] {
                    let diff = n - i
                    if isprime[diff] {
                        flag = true
                        print("\(n) = \(i) + \(diff)")
                        break
                    }
                }
            }
        }

        if !flag {
            print("Goldbach's conjecture is wrong.")
        }
    }
}

private func primeNumArr() -> [Bool] {
    var isprimenum = Array(repeating: true, count: 1000001)
    isprimenum[0] = false
    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
        }
    }
    return isprimenum
}

solution()

 

요즘, 시간복잡도에 대해서 생각하면서 푸는 빈도가 늘어나고 있다. 잘하고있는거겠지!! 알고리즘 고수가 되겠어 🫢 화이팅 🍀

https://jjalbot.com/tags/%ED%99%94%EC%9D%B4%ED%8C%85