BOJ :: 소수&팰린드롬 (no.1747)

Problem

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

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

Input

첫째 줄에 N이 주어진다.

Output

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

Guess

• 우선은 선형 탐색하면서,
• 소수일 경우, 팰린드롬일 경우를 계산하면 되겠다.
• 선형 탐색 : O(n)
• 소수 판별 : O(logn)
• 팰린드롬 판별: O(1/2n)

최종적으로, 상수를 제외하고 O(n^2) 로 예상한다.
N 범위가 백만까지라 제곱 복잡도로는 시간 초과가 날 수도 있겠다는 걱정은 들었지만..
다행히 첫 코드로 무사히 통과했다.

Solution

import sys
input = sys.stdin.readline

def solve(x):
    if x < 2: return 2

    while not isAnswer(x):
        x += 1
    return x

def isAnswer(x):
    if not isPalindrome(x): return False
    if not isPrime(x): return False

    return True

def isPalindrome(x):
    if x % 10 == 0: return False

    revertedNumber = 0
    while x > revertedNumber:
        quotient, remainder = divmod(x, 10)
        revertedNumber = revertedNumber * 10 + remainder
        x = quotient
    
    return x == revertedNumber or x == revertedNumber//10

def isPrime(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0: return False
    return True

n = int(input())
print(solve(n))

팰린드롬 함수가 조금 특별하게 보일 수 있을 것 같다.
보통은 string으로 변환한 다음 역순으로 바꾼 후 원문이랑 비교하는 식을 떠올릴거다.
그러나 자료형 변환이 생각보다 비용이 많이 들어서, 좋은 방식은 아니라고 생각했다.

• 123321 로 예를 들면,
• 123, 321 이렇게 반으로 나눈 다음
• 뒷부분인 321을 반전시킨 다음 첫부분인 123과 비교한다.
• 서로 같으면 팰린드롬인걸로 반환하는 방식이다.

왜 숫자 전체를 반전시키지 않았나?
정수 오버플로우를 고려해서다. (이 문제는 전체 반전시켜도 지장이 없긴 하다.)