알고리즘 문제(Swift) - 백준 6658 (골드바흐의 추측)

www.acmicpc.net​

 

에라토스테네스의 체 알고리즘을 이용하여 범위 내 소수를 판별하고 입력 값을 두 홀수 소수의 합으로 나타내는 문제이다

시간 제한이 0.5초라 여러 시도 끝에 성공했다

 

 

첫 번째 방법 → 재귀 함수 사용

• 우선 에라토스테네스의 체 알고리즘을 이용하여 n의 최대 값을 1,000,000으로 두고 소수 판별을 진행함
• 인덱스가 숫자가 되고 값이 true, false로 소수 판별되기 때문에 소수인 값만 필터링 후 인덱스 값을 primeNums 배열에 담아 소수로 이루어진 숫자 배열을 만듦
• 입력으로 들어온 값 num 보다 작은 수로만 이루어진 배열을 만듦
• 재귀함수를 이용하여 두 소수의 합이 num과 같은 모든 조합을 확인 후 소수의 차가 가장 큰 값을 출력

let maxNum = 1000000
var isPrime = Array(repeating: true, count: maxNum + 1)
isPrime[0] = false
isPrime[1] = false
for i in 2...Int(Double(maxNum).squareRoot()) {
    if !isPrime[i] {continue}
    for j in stride(from: i * i, through: maxNum, by: i) {
        isPrime[j] = false
    }
}

// 인덱스가 숫자가 되고 값이 true, false로 소수 판별되기 때문에 소수인 값만 필터링 후 
// 인덱스 값을 primeNums 배열에 담아 소수로 이루어진 숫자 배열을 만듦
let primeNums = isPrime.enumerated().filter{$0.1}.map{$0.0}

while let input = readLine(), let num = Int(input), num != 0{
    let filteredPrime = primeNums.filter{$0 <= num} // 입력으로 들어온 값 n 보다 작은 수로만 이루어진 배열을 만듦
    var maxNum = Int.min
    var answerArr = [String]()
    
    // 재귀함수를 이용하여 두 소수의 합이 num과 같은 모든 조합을 확인 후 소수의 차가 가장 큰 값을 출력
    func recur(index: Int, arr: [String]) {
        if arr.count == 2 {
            let a = Int(arr[0])!
            let b = Int(arr[1])!
            if a + b == num && maxNum < b - a {
                maxNum = b - a
                answerArr = arr
            }
            return
        }
        if index == filteredPrime.count {
            return
        }
        recur(index: index + 1, arr: arr + ["\\(primeNums[index])"])
        recur(index: index + 1, arr: arr)
    }
    
    recur(index: 0, arr: [])
    print("\\(num) = \\(answerArr.joined(separator: " + "))")
}

→ 이 코드는 while문을 돌 때마다 필터링하므로 비효율적

→ 재귀를 사용하여 모든 조합을 탐색하여 비효율적

→ 각 조합에서 두 소수의 차이를 계산하고 비교하는 작업이 중복되어 비효율적임

 

 

두 번째 방법 → 투 포인터

• 재귀문으로 모든 조합을 탐색하는 것이 아닌 소수 중 가장 작은 수부터 탐색
• 선택된 두 소수의 합이 num과 일치한다면 그게 가장 차이가 큰 소수 조합!

let maxNum = 1000000
var isPrime = Array(repeating: true, count: maxNum + 1)
isPrime[0] = false
isPrime[1] = false
for i in 2...Int(Double(maxNum).squareRoot()) {
    if !isPrime[i] {continue}
    for j in stride(from: i * i, through: maxNum, by: i) {
        isPrime[j] = false
    }
}
let primeNums = isPrime.enumerated().filter{$0.1}.map{$0.0}

while let input = readLine(), let num = Int(input), num != 0{
    let filteredPrime = primeNums.filter{$0 <= num}
    var left = 0
    var right = filteredPrime.count - 1
    var answer: (Int, Int)? = nil
    while left <= right {
        let sum = filteredPrime[left] + filteredPrime[right]
        if sum == num {
            answer = (filteredPrime[left], filteredPrime[right])
            break
        } else if sum < num {
            left += 1
        } else {
            right -= 1
        }
    }
    if let (a, b) = answer{
        print("\\(num) = \\(a) + \\(b)")
    } else {
        print("Goldbach's conjecture is wrong.")
    }
}

→ 첫 번째 방법과 마찬가지로 while문을 돌 때마다 필터링하므로 비효율적

 

 

세 번째 방법 → 필터링 제거

• 홀수 소수의 합으로 이루어진 수를 찾는 것이므로 3부터 num까지의 수를 차례로 검사
• 홀수이면서, 두 수가 소수면 탐색 종료!

let maxNum = 1000000
var isPrime = Array(repeating: true, count: maxNum + 1)
isPrime[0] = false
isPrime[1] = false
for i in 2...Int(Double(maxNum).squareRoot()) {
    if !isPrime[i] {continue}
    for j in stride(from: i * i, through: maxNum, by: i) {
        isPrime[j] = false
    }
}

while let input = readLine(), let num = Int(input), num != 0{
    for i in 3...num / 2 {
        if i % 2 != 0 && isPrime[i] && isPrime[num - i] {
            print("\\(num) = \\(i) + \\(num - i)")
            break
        }
        if i == num / 2 {
            print("Goldbach's conjecture is wrong.")
        }
    }
}