백준 1747번 풀이

taehoyoon·2023년 7월 1일

목록 보기

2/11

문제

문제

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

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

입력

첫째 줄에 N이 주어진다.

출력

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

예제 입력
31
예제 출력
101

풀이

1. 소수인지를 판별하는 함수

에라토스테네스의 체를 이용한 다양한 방법이 존재

내 나름대로 소수 판별하는 함수를 작성해봤지만, 시간 초과가 자꾸 떠서 결국 지선생의 도움을 받았다..

def is_prime(n):
    # 예외 처리
    if n <= 1:
        return False

    # n이 2, 3이면 당연히 소수
    elif n <= 3:
        return True

    # n이 2의 배수이거나 3의 배수이면 소수 아님
    elif n % 2 == 0 or n % 3 == 0:
        return False

    # 그 외의 경우를 위해 i에 5 할당
    i = 5

    # 2와 3을 제외한 모든 소수는 6의 배수 앞이나 뒤에 위치한다는 수학적 원리 이용
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6

    # 위 모든 경우가 아닐 때 n은 소수임.
    return True

❓왜 while i * i <= n: 일까?

해당 코드는 i가 n으로 나누어지는 지를 검사하는 부분이다.
만약 n이 i ✕ j로 표현된다면(i < j), i는 항상 √n보다 작다.
- 36의 경우 6✕6을 제외하면 전부 √36인 6보다 작은 수(2, 3, 4)로 나누어진다
따라서, 나누는 수 i는 √n보다 클 필요가 없다.

❓2와 3을 제외한 모든 소수는 6의 배수 앞이나 뒤에 위치한다?

모든 수는 6n+0, 6n+1, 6n+2, 6n+3,6n+4, 6n+5로 표현 가능하다.
이 중 6n, 6n+2, 6n+4는 2(3n), 2(3n+1), 2(3n+2)이기 때문에 2의 배수이다.
6n+3은 3(2n+1)이므로 3의 배수이다.
남은 수는 6n+1, 6n+5이고, 이 수는 6의 배수에서 ±1한 수이다.
즉, 2와 3을 제외한 모든 소수는 6의 배수에서 ±1한 수이다.

다시 코드를 살펴보자

    i = 5
    # 2와 3을 제외한 모든 소수는 6의 배수 앞이나 뒤에 위치한다는 수학적 원리 이용
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6

여기서 i에 5를 할당하고, 5와 7로 나누어지는 지를 검사
나누어진다면 소수가 아니므로, False를 반환
i에 6을 더해 while문으로 그 뒷 케이스도 반복 검사
나누는 수 i는 √n보다 클 필요가 없으므로 i * i <= n일 때까지만 while문 반복
위 모든 케이스를 통과했을 경우, 소수라고 판단

2. 팰린드롬 수 인지를 판별하는 함수

내가 구현한 함수

def is_pallindrome(n):
    if len(str(n)) <= 1:
        return True
    elif n[0] != n[-1]:
        return False
    else:
        return is_pallindrome(n[1:-1])

숫자를 문자열로 형변환한 뒤, 맨 처음 글자와 맨 마지막 글자를 비교하고 재귀함수를 통해 다음 케이스도 테스트하는 코드를 짰다.

근데..

스터디원이 풀은 코드를 보니 엄청 간단하게 구현하고 있었다

def is_palindrome(n):
    return str(n) == str(n)[::-1]

그냥 단순하게 거꾸로 정렬한 다음 원래 숫자와 같은 지만 검사하면 구현 가능했다..🤦‍♂️😱

소스코드

# 소수 판별 함수
def is_prime(n):
    if n <= 1:
        return False

    elif n <= 3:
        return True

    elif n % 2 == 0 or n % 3 == 0:
        return False

    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6

    return True


# 팰린드롬 수 판별 함수
def is_pallindrome(n):
    return str(n) == str(n)[::-1]


N = int(input())
while True:
    if is_pallindrome(N) and is_prime(N): # 팰린드롬 판별 함수가 더 빠르니 먼저 검사
        print(N)
        break
    else:
        N += 1