[백준] 1747번 : 소수&팰린드롬 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1747번: 소수&팰린드롬

 

1. 문제 설명

2. 풀이과정

에라토스테네스의 체를 이용하여 최대 범위에 해당하는 소수를 모두 구해 놓고 소수인 수들 중 N보다 크거나 같으면서 팰린드롬 수인 것을 찾아내면 되는 문제이다.
소수를 구하는 것은 에라토스테네스의 체로 쉽게 구할 수 있지만 팰린드롬 수를 판별할 때는 숫자의 값을 각 자릿수 별 리스트의 형태로 바꿔 판별해야 한다.
 
N의 범위는 1~1,000,000인데, 정답은 N보다 같거나 커야 한다. 최대 범위를 10,000,000으로 지정해 두고 정답을 구할 수도 있지만 그냥 각 N에 따라 N의 10배까지 최대 범위라고 생각하고 정답을 찾아도 그 안에 정답이 있으므로 괜찮다.
소수를 모두 구한 뒤에 N부터 차례대로 팰린드롬 수인지 판별한다.
팰린드롬 수인지 판별할 때는 숫자를 문자열로 바꿔 리스트 구조로 변한다.
이후 양쪽 끝에 각 포인터를 두고 해당 문자를 비교하며 계속적으로 일치하는지 판별하면 된다. (투 포인터 응용)
여기서 한 가지, N은 1이 될 수도 있지만 1은 소수가 아니므로 이 또한 고려해줘야 한다.
 
슈도코드

1. N(어떤 수) 입력받기
2. li(소수 리스트, 최대 범위 : N * 10)
3. for li 리스트 길이의 제곱근까지 반복:
   1. 소수가 아니면 넘어감
   2. for 소수의 배수 값을 li 리스트 길이까지 반복: 현재 수가 소수가 아님을 표시
4. N이 1일 수도 있지만 1을 소수가 아니므로 1을 소수가 아니라고 표시
5. for N ~ li 리스트 길이:
   1. 만약 해당 값이 소수이면
      1. 숫자값을 문자 형태의 리스트로 변환
      2. check(팰린드롬 수인지 판별)
      3. s(시작 인덱스)
      4. e(종료 인덱스)
      5. while (s < e): 만약 시작과 끝 인덱스에 해당하는 값이 다르면 팰린드롬 수 아님, 판별 종료
      6. 만약 해당 수가 팰린드롬 수이면 해당 수를 출력하고 정답을 구했으므로 종료

반응형

3. 소스코드

import sys
import math

N = int(sys.stdin.readline())

li = list(i for i in range(N * 10))
for i in range(2, int(math.sqrt(len(li)) + 1)):
    if (li[i] == 0):
        continue
    for j in range(i + i, len(li), i):
        li[j] = 0
li[1] = 0

for i in range(N, len(li)):
    if (li[i] != 0):
        num = list(str(li[i]))
        check = True
        s = 0
        e = len(num) - 1
        while (s < e):
            if (num[s] != num[e]):
                check = False
                break
            s += 1
            e -= 1

        if (check):
            print(li[i])
            break