[Python] 백준 2023 풀이

2023 계묘년, 새해 복 많이 받으세요 !

 

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

---

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

---

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

---

코드

import sys
import math
def prime_cal(prime_list):
    temp_list = []
    for i in prime_list:
        for j in range(10):
            now_n = i * 10 + j
            min_int = int(math.sqrt(now_n))
            for k in range(min_int, 1, -1):
                if now_n % k == 0:
                    break
                elif k == 2:
                    temp_list.append(now_n)
    prime_list = temp_list[:]
    return prime_list

N = int(sys.stdin.readline().strip())
prime_list = [2, 3, 5, 7]
for _ in range(N-1):
    prime_list = prime_cal(prime_list)
for i in prime_list:
    print(i)

소수 판정에 관한 계산은 prime_cal() 함수에서 진행하며, 함수의 파라미터는 리스트를 받았습니다.

 

초기에 prime_list 에 1의 자리에 속한 소수 2,3,5,7을 넣어두었습니다. 

 

 

첫번째 for문 : prime_list 안에 있는 원소들을 하나씩 가져옵니다.

 

두번째 for문 : prime_list 원소에 10을 곱하여 만약 첫번째 시행이라면, 10의 자릿수로 만든다음, 1씩 더하여 20, 21, 22 순으로 숫자를 만들어줍니다.

 

세번째 for문 : 본격적인 소수 판별이 일어나는 곳입니다.

소수 판정을 쉽게하려면 1에서 해당 수 까지 나눠서 알아내는 방법이 있지만, 조금이라도 시간을 줄이기 위해 제곱근을 이용해줍니다. 가운데에 있는 약수를 알아내어 나머지가 0이 나올 때까지 1씩 빼서 나누는 방법을 선택했습니다.

sqrt 제곱근 함수를 이용하여 제곱근 한 수 보다 작거나 같은 정수를 int함수로 알아냅니다.

그리고 그 수를 min_n에 저장합니다. min_n이란 아까 말씀드린 가운데에 있을 약수가 됩니다.

만약 k가 2가 될때까지도 나머지가 0이 나오지 않았다면, 소수라고 판정하고 temp_list에 append합니다.

 

모든 반복이 끝난 뒤에 prime_list 를 temp_list 로 바꿉니다.

 

 

이 문제에서 포인트를 길게 설명한 세번째 for문 이라고 생각하실지는 모르겠지만, 저는 두번째 for문을 포인트라고 생각합니다. 4자릿수를 입력한다고 해서 4자릿수에 해당하는 1000~9999 의 숫자를 모두 소수 판정을 하는게 아닌, 이전에 구한 소수에 10을 곱하고 1에서 9까지의 수를 더하여 소수 판정을 하는 것입니다.

 

제 코드에서 좀 더 보안할 점이 있다면, 두번째 for문에서 0~9의 숫자를 반복하지 않고 홀수인 1,3,5,7,9만 돌렸다면 좀 더 효율적인 코드가 되지 않았을까 싶네요. 어차피 짝수는 2로 나눠지니깐요.

---

후기

2023년 1월 1일, 새 해라 고른 2023번 문제인데 골드5라서 많이 쫄아있었습니다. 하지만 직접 풀어보니 생각만큼 어렵진 않았습니다. 기존 했던 소수 문제에 어떻게 해야 더 효율적인 코드를 짤 수 있을까에 대해 좀 더 생각할 부분이 있어서 오히려 재미있고 한번에 성공이 떠서 더 즐거웠습니다.

어떤 문제던 일단 겁먹고 시작하기 보다는 자신을 믿고 시작하는 한 해 보낼 수 있을것 같네요. 

올해도 화이팅!!

 

다들 새해 복 많이 받으세요!