[Python] 백준 1990번(소수인팰린드롬) 문제 풀이

 

 진짜 시간초과때문에 삽질을 엄청나게 많이 했던 문제였다...

 

 

 19시간이나 삽질을 하긴 했지만, 뭐, 결국 풀기는 했다.

 

import math

def is_palindrome(a):
    return a == "".join(list(reversed(a)))
    
def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True
    
a, b = list(map(int, input().split()))
for i in range(a, b+1):
    if is_palindrome(str(i)):
        if is_prime(i):
            print(i)
            
print(-1)

 

 처음에는 코드를 이렇게 짰다. 팰린드롬인 수 중 소수라면 출력하는 코드이다. 그런데 이 코드가 완벽했다고 생각했는데 시간 초과가 떴다.

 

import math
import sys

def is_palindrome(a):
    return a == "".join(list(reversed(a)))

def is_prime(n):
    if n == 1:
        return False
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n))+1, 2):
        if n % i == 0:
            return False
    return True
    
a, b = map(int,sys.stdin.readline().split())
for i in range(a, b+1):
    if is_palindrome(str(i)):
        if is_prime(i):
            print(i)
            
print(-1)

 

 몇 번의 삽질과 검색 후, input() 대신에 sys 모듈의 readline()을 쓰면 시간 초과가 안 뜨기도 한다길래 그렇게 바꾸어 봤다. 그리고 소수 판정 함수도 수가 너무 크면 반복문이 힘들 것 같아서 2의 배수면 바로 False를 반환하고, 반복문의 공차를 2로 하여 봤다. 그런데도 역시나 시간초과가 떴다. (도대체 뭐가 문젤까)

 

import math
import sys

def is_palindrome(a):
    return a == "".join(list(reversed(a)))
    
def binary_search(array, x):
    start = 0
    end = len(array) - 1 
    while start <= end:
        middle = (start + end) // 2
        if array[middle] == x:
            return True
        elif array[middle] < x:
            start = middle + 1
        else:
            end = middle - 1
    return False
    
a, b = map(int,sys.stdin.readline().split())

e = [False,False] + [True]*(b-1)
primes=[]

for i in range(2,b+1):
  if e[i]:
    primes.append(i)
    for j in range(2*i, b+1, i):
        e[j] = False

for i in range(a, b+1):
    if is_palindrome(str(i)):
        if binary_search(primes, i):
            print(i)
            
print(-1)

 

 그래서 이번에는 에라토스테네스의 체 알고리즘과, 이진 탐색 알고리즘을 사용해 보았다. 이거야말로 메모리 초과는 뜨더라도 시간 초과는 절대 뜰 수 없는 코드였다. 그런데 이것마저 시간 초과가 떴다. 그래서 "내일 생각해보자"하고 그냥 잤다. 그래서 자고 일어나서 생각을 해 봤다. 생각해보니 어차피 2의 배수에서는 소수가 나올 수가 없는데, 내가 반복문을 2의 배수까지 싹 돌리고 있음을 알아냈다. 반복문의 공차를 2로 하면 시간은 1/2만큼 걸릴 것이다.

 

import math
import sys

def is_palindrome(a):
    return a == "".join(list(reversed(a)))
    
def binary_search(array, x):
    start = 0
    end = len(array) - 1 
    while start <= end:
        middle = (start + end) // 2
        if array[middle] == x:
            return True
        elif array[middle] < x:
            start = middle + 1
        else:
            end = middle - 1
    return False
    
a, b = map(int,sys.stdin.readline().split())

e = [False,False] + [True]*(b-1)
primes=[]

for i in range(2,b+1):
  if e[i]:
    primes.append(i)
    for j in range(2*i, b+1, i):
        e[j] = False

if a % 2 != 0:
    for i in range(a, b+1, 2):
        if is_palindrome(str(i)):
            if binary_search(primes, i):
                print(i)
                
else:
    for i in range(a+1, b+1, 2):
        if is_palindrome(str(i)):
            if binary_search(primes, i):
                print(i)
                
print(-1)

 

 이것마저 시간초과가 떴다. 하아... 그래서 한번 질문 게시판을 찾아 보았다. 나와 같이 시간 초과로 고통을 겪는 여러 사람이 있었다.

 

 

 이런 글을 찾았다!! 수행시간이 1/10 정도로 감소하다니, 이거야말로 내가 찾던 글이었다. 그리고, 게시판을 찾아보던 와중 에라토스테네스의 체 알고리즘이 메모리 초과가 뜬다고 해서 그것도 바꾸었다. 하긴, 생각해 보면 b가 100,000,000까지 들어오는데 길이가 100,000,000인 리스트를 만들면 당연히 메모리 초과가 뜰 것이다.

 

import math
import sys

def is_palindrome(a):
    return a == "".join(list(reversed(a)))
    
def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True
    
a, b = map(int,sys.stdin.readline().split())

if a % 2 != 0:
    for i in range(a, b+1, 2):
        if len(str(i)) % 2 == 0 and i % 11 != 0:
            continue
        if is_palindrome(str(i)):
            if is_prime(i):
                print(i)
                
else:
    for i in range(a+1, b+1, 2):
        if len(str(i)) % 2 == 0 and i % 11 != 0:
            continue
        if is_palindrome(str(i)):
            if is_prime(i):
                print(i)
                
print(-1)

 

 그래서 "이 코드야말로 정말 마지막"이라는 생각으로 이렇게 코드를 짰다. 확실히 효과가 있었다. 전 코드까지는 4%에서 시간 초과가 떴는데, 이 코드는 54%까지 갔다. 그래서 조금만 더 하면 되겠다는 생각으로 구글링을 더 해보았다.

 

 

 그러다 나와 같은 문제로 고통받던 분 중 한 명이 이런 블로그를 올려주신 것을 볼 수 있었다. 와우! 이제 함수 안에서 돌아가는 반복문을 제외하면 반복문은 최대 4,999,997번밖에 안 돌릴 수 있다!

 

import math
import sys

def is_palindrome(a):
    return a == "".join(list(reversed(a)))
    
def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True
    
a, b = map(int,sys.stdin.readline().split())

if b > 10000000:
    b = 10000000

if a % 2 != 0:
    for i in range(a, b+1, 2):
        if len(str(i)) % 2 == 0 and i % 11 != 0:
            continue
        if is_palindrome(str(i)):
            if is_prime(i):
                print(i)
                
else:
    for i in range(a+1, b+1, 2):
        if len(str(i)) % 2 == 0 and i % 11 != 0:
            continue
        if is_palindrome(str(i)):
            if is_prime(i):
                print(i)
                
print(-1)

 

 그런데 이것마저 시간 초과가 떴다. 이제 이 이상으로 시간 복잡도를 줄일 수는 없을 것이다 확신하던 참이었다. 그런데도 시간초과가 뜨다니, 절망하던 찰나 내 눈에 어떤 것이 들어왔다. 바로 is_palindrome() 함수! 팰린드롬인지 아닌지를 판별하는 함수인데, 생각해 보니 이것도 리스트로 바꾼 뒤 다시 붙이는 거라 시간이 꽤 걸릴 수도 있겠다 생각했다. 파이썬에는 [::-1]이라고, 바로 문자열이나 리스트를 역순으로 바꾸는 기능도 있는데 말이다.

 

import math
import sys

def is_palindrome(a):
    return a == a[::-1]
    
def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True
    
a, b = map(int,sys.stdin.readline().split())

if b > 10000000:
    b = 10000000

if a % 2 != 0:
    for i in range(a, b+1, 2):
        if len(str(i)) % 2 == 0 and i % 11 != 0:
            continue
        if is_palindrome(str(i)):
            if is_prime(i):
                print(i)
                
else:
    for i in range(a+1, b+1, 2):
        if len(str(i)) % 2 == 0 and i % 11 != 0:
            continue
        if is_palindrome(str(i)):
            if is_prime(i):
                print(i)
                
print(-1)

 

 마침내, 맞을 수 있었다. 와, 정말 삽질을 많이 했다. 글에 올라온 것보다 1번정도 더 많이 제출했으니. 그래도 뭐, 맞았으니 된 건가. 골드 문제를 처음 풀어 본 건데, 앞으로 골드 문제도 많이 풀어야겠다.