[백준] (Swift 스위프트) 17103번 - 골드바흐 파티션

 

문제 링크

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

17103번: 골드바흐 파티션

 

문제 해결 아이디어

1. 함수 isPrimeNumber
   • 현재 입력받은 수까지 무슨 소수가 존재하는지 배열로 정리
   • 예를들어 9가 입력되면, [2, 3, 5, 7] 이 반환된다.
2. main
   • 입력받은 num 까지 무슨 소수가 존재하는지 isPrimeNums 배열 생성
   • 2부터 num/2 까지 반복
     • 왜 num/2 냐? 10을 예로 들면, (3, 7), (5, 5) (7, 3) 이렇게 골드바흐 파티션이 3쌍이 존재하게 된다. 하지만 문제 설명해서 이렇게 된 경우, 순서가 뒤바뀌어도 하나로 취급한다고 했기에, 답은 3쌍이 아니라 2쌍이 된다. 따라서 num/2 까지 루프를 돌게되면, 뒤에 반복되는 것들은 count 하지 않기 때문에 num/2 로 범위를 설정했다.
   • j와 num - j 가 모두 primeNums 배열에 존재한다면, count+1

이 아이디어를 그대로 코드로 구현했다.

 

내가 푼 풀이 - 시간초과

*------------ 시간초과 ----------------*/
import Foundation

let n = Int(readLine()!)!

//소수 생성 함수
func isPrimeNumber (n: Int) -> Array<Int> {
    var primeNums: [Int] = []
    var check = Array(repeating: true, count: n+1)
    check[0] = false
    check[1] = false

    for i in 0..<n+1 {
        if check[i] == true {
            var j = 2

            while (i*j) <= n {
                check[i*j] = false
                j += 1
            }
        }
    }

    for i in 0..<check.count {
        if check[i] == true {
            primeNums.append(i)
        }
    }
    return primeNums
}


///입력받기
for i in 0..<n {
    let num = Int(readLine()!)! //입력받은 수
    var count = 0
    let primeNums = isPrimeNumber(n: num) //입력받은 num까지 존재하는 소수

    for j in stride(from: 2, through: num/2, by: 1) {
        if primeNums.contains(j) { //num-j한 결과가 소수면 count+1
            if primeNums.contains(num-j) {
                count+=1
            }
        }
    }

    print(count)
}

 

 

내가 푼 풀이 - 맞았습니다!

비교적 왜 시간초과인지 빠른 시간내로 찾을 수 있었다. 가장 시간을 빠르게 줄일 수 있는 반복문 먼저 살펴보면서 범위를 수정해주었고, 2차로 또 시간초과가 뜨길래 두번째로 소수생성함수를 Int로 바꾸는 과정을 줄여줌으로써 시간초과를 해결 할 수 있었다.

• 소수 생성 함수
  • for 문 돌 때 0부터 n+1 돌게됨
  • 이렇게 하게되면 시간복잡도 O(N)
  • 범위 2 ~ n에서 n의 제곱근값보다 작은 부분들에 대한 처리가 끝나면, 제곱근값보다 큰 부분의 값 또한 처리가 된다는 말
  • 시간복잡도를 sqrt 제곱근을 사용해서 줄여줄 수 있다.
• 소수 생성함수 bool → Int
  • 이렇게 하는 과정에서 시간복잡도가 더 추가된다.
  • 따라서 그냥 Bool 형태로 반환해주고, index를 활용해보자.

import Foundation

let n = Int(readLine()!)!

//소수 생성 함수
func isPrimeNumber (n: Int) -> Array<Bool> {
    var check = Array(repeating: true, count: n+1)
    check[0] = false
    check[1] = false

    for i in 0..<Int(sqrt(Double(n)))+1 {
        if check[i] == true {
            var j = 2

            while (i*j) <= n {
                check[i*j] = false
                j += 1
            }
        }
    }
    return check
}


//입력받기
for i in 0..<n {
    let num = Int(readLine()!)! //입력받은 수
    var count = 0
    let primeNums = isPrimeNumber(n: num) //입력받은 num까지 존재하는 소수

    for j in stride(from: 2, through: num/2, by: 1) {
        if primeNums[j] == true { //num-j한 결과가 소수면 count+1
            if primeNums[num-j] == true {
                count+=1
            }
        }
    }

    print(count)
}

 

 

이 문제의 핵심은 소수를 구할 때 에라토스테네스의 체 를 사용하는 것이었다.

에라토스테네스 체 란?

대량으로 빠르게 소수를 구하는 알고리즘이다.

▷ 에라토스테네스 체 원리

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

1. 배열을 생성하여 초기화한다. (원하는 숫자만큼 true 던, 0으로던 배열을 초기화)
2. 2부터 시작해서 특정 수의 배수가 되는 수를 모두 지운다. (지울 때 자기 자신은 지우지 않고 (소수이기 때문) 이미 지워진 수는 건너뛴다.)
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

 

에라토스테네스의 체를 왜 대량으로, 빠르게 구할때 사용할까? 그 이유는 에라토스테네스 체 알고리즘의 시간복잡도는 거의 선형에 가까운운 굉장히 빠른!! O(Nlog(logN)) 시간 복잡도를 가진다. 따라서 빠르고, 정확하게, 대량의 소수를 구할 때 사용할 수 있는 것이다.