[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] k진수에서 소수 개수 구하기

문제를 정리해보자.

 

양의 정수 n이 주어진다.

이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 조건에 맞는 소수가 몇 개인지 찾으면 된다.

 

조건은 아래와 같다. ( P는 소수[Prime Number]를 의미한다.)

 

1. 소수 양쪽에 0이 있는 경우 : 0P0

2. 소수 오른쪽에만 0이 있는 경우 : P0

3. 소수 왼쪽에만 0이 있는 경우 : 0P

4. 소수 양쪽에 아무것도 없는 경우 : P

 

단, P는 각 자릿수에 0을 포함하지 않는 소수이다. 예를 들어, 101은 P가 될 수 없다.

 

 

---

 

풀이를 생각해보자.

 

예를 들어, 437674을 3진수로 바꾸면 211020101011이다.먼저, 211020101011안에서 조건에 맞는지 확인할 수를 찾자.

 

 

수기 작성

 

 

( N는 수[Number]를 의미한다.)

 

0을 기준으로 좌우를 각각 그룹화를 해보자.

앞은 N0, 중간은  N, 뒤는 0N 형태가 나타난다.

따라서 N이 P이기만 하면, 조건에 만족하는 소수가 된다.

 

N이 P인지 판별해보자.

소수는 1과 그수 자신 이외의 자연수로는 나눌 수 없는, 1보다 큰 자연수이다. 출처

따라서 2부터 자기 자신의 제곱근까지 나눴을 때, 나눌 수 없다면 소수이다.

(예를 들어, 49는 7까지만 나눠봐도 소수임을 판별할 수 있다.)

 

추가로 조건 4의 경우는, 0없이 양의 정수만 있는 경우가 해당한다. 예를 들어, 5

 

 

---

 

구현해보자.

 

 

import string
import math

tmp = string.digits+string.ascii_lowercase


# 10진수 → N진수 변환
def convert(num, base):
    q, r = divmod(num, base)
    if q == 0:
        return tmp[r]
    else:
        return convert(q, base) + tmp[r]


def solution(n, k):
    result = convert(n, k)
    li = result.split('0')

    answer = 0

    # 소수 판별
    for num in li:
        if num == '' or num == '1':
            continue

        num = int(num)
        sosu = True

        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                sosu = False  # 소수 아님
                break

        if sosu:
            answer += 1

    return answer


print(solution(1, 10))

 

 

---

 

시행착오

 

for i in range(2, num):
for i in range(2, int(math.sqrt(num)) + 1):

 

첫 번째 줄로 코드를 작성했을 때는 시간초과가 난다.

두 번째 줄로 바꾸니 통과되었다.

 

이유는 수가 엄청 큰 '소수'라면 break에 걸리지 않아서, range의 범위에 따라 시간초과가 발생할 수 있기 때문이다.

 

 

첫 번째 줄로 작성한 결과