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

문제

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

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

입력

첫째 줄에 N이 주어진다.

출력

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

예제 입력 1 복사

31

예제 출력 1 복사

101

 

[소스 코드]

 

쉬운 문제라고 생각했는데 '틀렸습니다'와 시간 초과 때문에 여러 번 다시 푼 문제이다.

평소에 수의 범위를 크게 신경 쓰지 않고 문제를 풀었는데 이 문제는 범위 때문에 틀렸다.

 

1은 소수에 포함이 안되지만 입력에는 소수가 있고, 답 또한 입력된 수와 같을 수 있기에 고려해 주어야 한다.

이를 소수를 판별하는 함수에서 걸러주거나, 그 이후에 걸러주어야 하는데 전혀 생각하지 못했다.

 

또한 입력의 제한이 있었기에 for문의 범위를 쉽게 지정할 수 있었는데

결과값은 이 범위에 한정되지 않는다는 사실을 간과했다.

구하려는 수가 조건을 만족하는 수중에 가장 작은 수이기 때문에

1000000을 넘는 수중에 조건을 만족하는 수를 찾아서 예외처리해주면 되기에 어렵진 않았지만

신경 쓰지 않으면 틀리기 쉬운 부분인 것 같다.

 

import math

n = int(input())

def is_p(x): #소수인지 확인하는 함수
    count = 0
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0: 
           return False
    return True
    
result = 0
for i in range(n, 1000001): #n보다 크거나 같고, 1000000보다 작거나 같은
    if i==1: #입력에 1이 포함되므로 1일 경우는 걸러줘야 함(소수가 아님)
        continue
    if is_p(i): 
        if str(i) == str(i)[::-1]: #문자열로 형변환하여 거꾸로 만듬
            result = i
            break
            
if result == 0: 
    result = 1003001
    #입력의 제한은 1000000까지지만 결과의 제한은 없음 
    #1000000보다 결과가 크면 result값은 0이므로, 조건에 맞는 수를 result값에 넣어줌
    
print(result)