[파이썬/Python] 백준 1747번 소수&팰린드롬

[파이썬/Python] 백준 1747번 소수&팰린드롬

1747번: 소수&팰린드롬

---

문제

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

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

해설

문제에서 요구하는 사항

1. N의 범위 (1 ≤ N ≤ 1,000,000)

2. 결과 값은 N보다 크거나 같아야 한다.

3. 결과 값은 소수여야 한다.

[알고리즘] 소수 판별법 (Primality Test)

4. 결과 값은 팰린드롬인 수 중에서 가장 작은 수여야 한다.

코드

import math

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

def isPalindrome(x):
    if str(x) == str(x)[::-1]:
        return True
    return False

N = int(input())
while True:
    if isPrime(N) and isPalindrome(N):
        print(N)
        break
    N += 1

풀이

import math

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

1. 소수를 구하는 함수 isPrime이다. 1은 소수가 아니므로 예외처리를 해주어야 한다.

 

소수를 구하는 알고리즘의 자세한 내용은 아래 링크를 참고하자.

[알고리즘] 소수 판별법 (Primality Test)

 

def isPalindrome(x):
    if str(x) == str(x)[::-1]:
        return True
    return False

2. 팰린드롬 수를 구하는 함수이다. 팰린드롬 수를 구하는 방법은 리스트 슬라이싱에서 아이디어를 얻을 수 있었다.

원래 수와 이를 역순으로 나타낸 수가 서로 일치할 경우 True를 반환하여 팰린드롬 수임을 판별하였다.

 

리스트 슬라이싱의 자세한 내용은 아래 링크를 참고하자.

11. 파이썬 리스트 슬라이싱 활용하기 - Codetorial

 

N = int(input())
while True:
    if isPrime(N) and isPalindrome(N):
        print(N)
        break
    N += 1

3. N을 입력받아 무한루프를 통해 소수이면서 동시에 팰린드롬 수인 경우 N을 출력하였다.

둘 중 하나라도 해당하지 않을 경우 N을 증가시켜 문제 조건에 해당하는 수를 찾는다.

피드백

내 코드는 지나치게 실행 시간이 느렸다.

 

다른 사람들 중 파이썬으로 푼 사람들의 채점 현황과 실행 시간을 비교해보았는데,

가장 큰 특징은 나와 같이 실행 시간이 큰 사람들의 공통점은 isPalindrome(x) 즉 팰린드롬 수를 판별하는 메소드를 따로 선언해주었다는 점이다.

 

소수를 판별하는 메소드는 큰 차이를 발생시키지 않는 것 같은데, 메소드를 호출하고 문자열로 형변환하는 과정이 실행시간에 큰 영향을 미치는걸까?