[백준 #1747 파이썬] 재귀, 완전탐색

소수를 판정하는 것과  팰린드롬을 판정해주는 함수를 각각 만든다.

그리고 시간복잡도를 따져 둘 중에 무엇을 먼저 해주어야 시간 복잡도가 낮을 지 고민을 해야한다.

처음에는 소수를 판정하는 것이 더 적을 것이라고 생각했지만, 팰린드롬이 탐색에 있어서 더 효율적이었다..

 

그리고 꼭 고민해주어야 할것은 n의 범위였다. n이 1인 경우도 고려하고 있으므로 이것에 대한 별도의 처리가 필요하다.

다만, 인터넷 사이트의 결과들을 보면 다른 사람들은 100만 이상의 소수를 따로 처리를 해주었는데 나는 그럴 필요는 없었다!

 

리턴값을 너무 마음대로 num으로 하긴 했는데 전혀 그럴 필요는 없어보인다 ㅎㅎ

 

def is_palindrome(num):
    if str(num) != str(num)[::-1]:
        return False
    return num

def is_prime(num):
    if num == 1:
        return False
    for i in range(2,num-1):
        if num % i == 0:
            return False
    return num


n = int(input())

while True:
    if is_palindrome(n) == False:
        n += 1
    else: 
        if is_prime(n) == False:
            n += 1
        else:
            print(n)
            break