[2022 KAKAO BLIND RECRUITMENT] k진수에서 소수 개수 구하기

문제조건

양의 정수 n을 k진수로 변환하여 조건에 맞는 소수를 출력해야 한다. 조건은 아래와 같다.

• 0P0처럼 소수 양쪽에 '0'이 있는 경우
• P0 | 0P 처럼 소수 오른쪽 혹은 왼쪽에 0이 있고 다른 쪽엔 아무것도 없는 경우
• P 소수만 있는 경우
• 단, P는 각 자릿수에 0이 없다

제출 코드

import math

def is_prime(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False 
    return True 

def convert(n, k):
    rev_base = '' 
    while n > 0:
        n, mod = divmod(n, k)
        rev_base += str(mod)
    return rev_base[::-1] 

def solution(n, k):
    answer = 0
    num = convert(n,k)
    for n in num.split('0'):
        if n == '' or n == '1':
            continue
        else: 
            if is_prime(int(n)):
                answer += 1

    return answer

풀이

convert를 통해 k진수로 변환하고, 0을 기준으로 잘라 prime number인지 판별했다.
잘라낸 p의 개수를 셌을 때, 1은 소수로 세지 않는 것처럼 보였다. 그래서, 0을 기준으로 자른 숫자들을 확인하면서 1은 건너뛰어 줬다.

뭔가 다른 조건이 숨겨져있지 않을까 걱정한게 더 시간을 끌게하는 요인이었다.