백준 1747번 소수&팰린드롬 - SWIFT

문제

---

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다.

 

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

 

문제 링크

1747번: 소수&팰린드롬

 

풀이

---

이 문제를 풀 때 함수 여러개를 이용해서 조금 복잡하게 풀긴 했다.

하지만 동작 과정 자체는 복잡하지는 않다.

동작 과정은 아래와 같다.

1. 현재 수 보다 크거나 같은 첫번째 팰린드롬 수를 찾는다.
2. 소수 인지 체크해본다.

동작 과정의 큰 틀은 간단하나, 그 세부 내용을 짜는데 약간의 어려움이 있어서 코드가 복잡해졌다.

동작 과정을 보기 전에 이 문제의 핵심인 팰린드롬 수 찾기부터 보자.

 

프로그램 동작

---

팰린드롬 수 찾기 / 만들기

팰린드롬 수는 데칼코마니와 비슷해서, 중앙을 잡고 좌, 우를 대칭 시켜주면 만들어진다.

 

하지만 다음 팰린드롬 수를 원한다면, 값을 늘려줘야한다.

팰린드롬 수는 대칭이기 때문에 일반적인 10진수 처럼 가장 뒤에 있는 값을 하나 늘려주게 되면, 가장 앞에 있는 값도 하나 늘어나게 되서 수가 급격하게 커지게 된다.

 

그래서 바로 다음 팰린드롬 값을 알고 싶다면, 가장 중앙값 부터 하나씩 늘려줘야 한다.

이런 식으로 값을 키워나가면 다음 팰린드롬 수를 찾을 수 있다.

 

...라고 생각하면 모든 경우를 생각한게 아니게 된다.

 

내가 키우려는 숫자가 9일때를 생각해야한다.

가운데 수가 9이면 10진수 계산하듯 자릿수를 넘겨줘야한다.

 

만약에 이번에 키우려는 숫자가 9인데, 다음 수도 9이고, 다다음 수도 9이면?

그러면 물결 치듯 다음 수를 하나씩 키워줘야한다.

각 자릿수 마다 팰린드롬 수는 하나 이상 씩 있을 것인데, 그 중 가장 큰 팰린드롬수는 당연히 전부다 9로 이루어진 수일 것이다.

이 팰린드롬 수의 다음 수를 구하려면 다음 자릿수로 넘어가야하므로, 자릿수를 하나 늘려주면 된다.

이런 과정을 거치고 나면, 다음 팰린드롬 수를 구할 수 있다.

 

소수인지 체크

앞에서 팰린드롬 수를 구했으니 이제 소수인지만 체크하면 된다.

단일 수가 소수인지, 아닌지를 체크하는 방법은 다음과 같다.

 

해당 수를 2부터 해당 수의 제곱근 까지 나눠보는 것

 

제곱근 까지만 나누는 이유에 대해서는 아래의 글에 써 놓았다. ▼

간단한 수학(+ 약간의 정수론)

 

팰린드롬 수 찾기/만들기와 소수인지 체크를 수행하면 답이 나온다.

 

 

Swift 코드

---

import Foundation

let N = readLine()!
var arr = [Int]()
var pal = [Int]()
var nin = [Int]()

for i in N {
    arr.append(Int(String(i))!)
}

func makeBigger(_ mid1: Int, _ mid2: Int) {
    if pal[mid1] == 9 {
        pal[mid1] = 0
        pal[mid2] = 0
        makeBigger(mid1 - 1, mid2 + 1)
    } else {
        if mid1 != mid2 {
            pal[mid1] += 1
            pal[mid2] += 1
        } else {
            pal[mid1] += 1
        }
    }
}

func atoi(_ arr: [Int]) -> Int {
    var sum = 0
    for i in arr {
        sum *= 10
        sum += i
    }
    return sum
}

func nextPal() -> Int {
    pal = arr
    nin = Array(repeating: 9, count: arr.count) 

    if arr == nin {
        for i in 0..<arr.count {
            pal[i] = 0
        }
        pal.append(1)
        pal[0] = 1
        arr = pal
        return atoi(pal)
    }
    for i in (arr.count / 2)...(arr.count - 1) {
        pal[i] = arr[arr.count - i - 1]
    }
    if pal == arr {
        if pal.count % 2 == 0 {
            makeBigger(arr.count / 2 - 1, arr.count / 2)
            arr = pal
            return atoi(pal)
        } else {
            makeBigger(arr.count / 2, arr.count / 2)
            arr = pal
            return atoi(pal)
        }
    }
    for i in (arr.count / 2)...(arr.count - 1) {
        if pal[i] < arr[i] {
            if pal.count % 2 == 0 {
                makeBigger(arr.count / 2 - 1, arr.count / 2)
                arr = pal
                return atoi(pal)
            } else {
                makeBigger(arr.count / 2, arr.count / 2)
                arr = pal
                return atoi(pal)
            }
        } else if pal[i] > arr[i] {
            arr = pal
            return atoi(pal)
        }
    }
    arr = pal
    return 0
}

func primeChecker(_ pal: Int) -> Bool {
    if pal == 1 {
        return false
    } else if pal == 2 {
        return true
    } else if pal == 3 {
        return true
    }
    let root = Int(sqrt(Double(pal)))
    for i in 2...root {
        if pal % i == 0 {
            return false
        }
    }
    return true
}

while true {
    let tmp = atoi(arr)
    var flag = true
    for i in 0..<arr.count / 2 {
        if arr[i] != arr[arr.count - i - 1] {
            flag = false
            break
        }
    }
    if flag {
        if primeChecker(tmp) {
            print(tmp)
            break
        }
    }
    let answer = nextPal()
    if primeChecker(answer) {
        print(answer)
        break
    }
}

 

코드를 상당히 복잡하게 짜서, 최선의 방법은 절대 아니다.