[백준_1747]소수&팰린드롬 with Python

백준(BOJ): 소수&팰린드롬(골드 5)

문제 출처: https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

1. 알고리즘

어렵진 않은데...시간초과 났었음. 소수를 계산하는 부분에 대해 모든 수에 대해 각각 소수를 구하려하면 Python은 시간초과... 문제에서 나올 수 있는 가장 큰 수까지의 소수를 처음 한 번만 구해두고 그 친구들을 가지고 찾아야 한다.

• 입력받는 수 1,000,000 보다 크거나 같고, 소수이면서 팰린드롬인 수인 가장 작은 수는 1,003,001 ▶ 1,003,002까지 소수임을 판별
  • 에라토스테네스의 체, check_prime 함수 사용
  • 2부터 num 제곱근까지 반복. 소수 판별 리스트 eratos[n]이 True로 소수일 경우, n의 배수를 전부 False로 바꿔줌.
  • n의 배수를 바꾸기 때문에, num의 제곱근까지만 반복하면 num까지 모든 수에 대해 연산이 가능
• 팰린드롬 = 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수
  
  • string 데이터타입은 [::-1]으로 쉽게 순서를 뒤집을 수 있으므로 number를 string 값으로 바꿔서 비교
• 숫자 N부터 1씩 증가하며 반복문 시작
  • 팰린드롬이고, 소수이면 break. 숫자 출력

 

 

2. 유의 사항

 

3. 어려웠던 점, 해결방법

• 처음에 생각없이 숫자 N부터 1씩 증가시키며 각 수에서 소수를 각자 계산했었음. 시간초과.

  • #시간초과 코드
    def is_prime(num):
        eratos = ([False] * 2) + ([True] * (num-1))
    
        m = int(num**0.5)
        for n in range(2, m+1):
            if eratos[n]:
                for idx in range(n+n, num+1, n):
                    eratos[idx] = False
    
        return eratos[num]
    """
    생략
    """
        number = N
        while True:
            if str(number) == str(number)[::-1]:
                if is_prime(number):
                    break
    
            number += 1

  • 가장 큰 수를 대상으로 소수 판별 리스트를 만들고, 그 리스트를 참조하여 소수인지 판별하도록 함.

 

4. 소스코드

상세 설명은 주석 참고

import sys
 
#소수 판별 리스트 생성 함수
def check_prime(num):
        
    #num의 제곱근까지만 반복
    m = int(num**0.5)
    for n in range(2, m+1):
        #현재 n이 소수이면
        if eratos[n]:
            #n의 배수를 전부 False(=소수 아님) 처리
            for idx in range(n+n, num+1, n):
                eratos[idx] = False
    
    #의미 없음. 위에서 만든 eratos 리스트를 판별 용도로 사용
    return eratos[num]
 
 
input_func = sys.stdin.readline
if __name__ == '__main__':
    N = int(*map(int, input_func().split()))
    
    #0, 1은 소수가 아니므로 False, 2부터 TRUE로 된 초기 리스트 생성
    eratos = ([False] * 2) + ([True] * (1003002))
    #최대 1003002까지의 소수를 판별
    check_prime(1003002)
    
    #N보다 크거나 같아야 하므로 N부터 시작
    number = N
    while True:
        #팰린드롬 검사
        if str(number) == str(number)[::-1]:
            #소수 검사
            if eratos[number]:
                break
        
        #두 검사 모두 True 값이 아니면 숫자+1
        number += 1
    
    #결과 출력
    print(number)

 

5. 고민

• 처음에 팰린드롬 검사할 때, 숫자를 반으로 쪼개서 앞 뒤를 비교했었는데...왜 안됐을까? 뒤집어서 같은 숫자면, 앞 절반이랑 뒤 절반 뒤집어서 비교해도 같으면 팰린드롬인 거 아닌가. 그냥 내 코드 문제였나...?