알고리즘 문제(Swift) - 백준 1747 (소수 & 팰린드롬)

www.acmicpc.net​

 

입력 N보다 큰 소수이면서, 팰린드롬인 가장 작은 수를 구해야 하기 때문에,

에라토스테네스의 체 알고리즘을 사용하여 최대 값인 1,000,000까지의 소수를 판별 후

N 보다 큰 수를 돌면서 소수인지 확인 및 팰린드롬인 수인지 확인해야 함

 

첫 번째 시도

팰린드롬인 수 판별을 투 포인터를 이용하여 구현 → 테스트 케이스는 통과하지만, “틀렸습니다”

let maxNum = 1000000
var isPrime = Array(repeating: true, count: maxNum + 1)
isPrime[0] = false
isPrime[1] = false

for i in 2...maxNum {
    if !isPrime[i] { continue }
    for j in stride(from: i * i, through: maxNum, by: i) {
        isPrime[j] = false
    }
}

// 소수 배열 (isPrime 배열의 true 값을 가진 index가 바로 소수인 숫자)
let primeNum = isPrime.enumerated().filter{$0.1}.map{$0.0}

// 팰린드롬 수인지 판별
func isPalindrome(num: Int) -> Bool {
    let str = String(num).map{$0}
    var left = 0
    var right = str.count - 1
    
    while left <= right {
        if str[left] == str[right] {
            left += 1
            right -= 1
        } else {
            return false
        }
    }
    return true
}

let N = Int(readLine()!)!

for i in N...maxNum {
    if isPrime[i] && isPalindrome(num: i) {
        print(i)
        break
    }
}

 

두 번째 시도

문제를 읽고 또 읽어보니 “N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는” 에서 이 수가 N의 최대 값 (1,000,000)보다 작다고 한 적은 없었다..

따라서, 출력 값은 1,000,000보다 클 수도 있다!

→ maxNum의 범위를 더 큰 수로 변경하니 통과되었다.

let maxNum = 2000000 // 1,000,000보다 큰 수로 변경
var isPrime = Array(repeating: true, count: maxNum + 1)
isPrime[0] = false
isPrime[1] = false

for i in 2...maxNum {
    if !isPrime[i] { continue }
    for j in stride(from: i * i, through: maxNum, by: i) {
        isPrime[j] = false
    }
}

// 소수 배열 (isPrime 배열의 true 값을 가진 index가 바로 소수인 숫자)
let primeNum = isPrime.enumerated().filter{$0.1}.map{$0.0}

// 팰린드롬 수인지 판별
func isPalindrome(num: Int) -> Bool {
    let str = String(num).map{$0}
    var left = 0
    var right = str.count - 1
    
    while left <= right {
        if str[left] == str[right] {
            left += 1
            right -= 1
        } else {
            return false
        }
    }
    return true
}

let N = Int(readLine()!)!

for i in N...maxNum {
    if isPrime[i] && isPalindrome(num: i) {
        print(i)
        break
    }
}