2022 카카오 신입공채 코딩테스트(2)

두 가지 함수만 구현하면 쉽게 풀 수 있다.
1. 진법 변환
2. 소수 판별

문제 내의 0과 관련된 자세한 설명은 파이썬에서 0을 기준으로 split하면 해결 될 문제이다. 그냥 0을 기준으로 0을 제외한 숫자가 소수인지 아닌지 알아보면 되기 때문이다.

진법 변환

십진수를 n진수로 변환하는 방법은 따로 구현된 함수가 없기 때문에 간단하게 구현했다. n진수를 만들기 위해서는 기존의 숫자를 n으로 계속 나누어가면 된다.

소수 판별

소수인지 아닌지 판별하는 방법에는 두 가지가 있다.
먼저 2부터 $\sqrt{n}$까지 나누어 떨어지는 수가 없으면 소수이다. 이 방식이 아래에 구현한 prime 함수이다.
두 번째 방법은 에라토스테네스의 체를 사용하면 된다. 해당 내용은 노션 페이지에 정리해 두었다.
만약 첫 번째 방법으로 시간초과가 됐다면 에라토스테네스의 체를 사용했을 것이다.

첫 번째 방법은 하나의 수가 소수인지 아닌지 판별하는데 용이하다면, 에라토스테네스의 체는 n까지의 모든 소수를 구할 수 있다.

문제 해결

그래서 두 함수만 구현하면 문제 해결은 쉽다.

• 진법 변환 후 0으로 split
• 위의 리스트를 순회하면서 소수이면 answer += 1
• 이때 split의 결과가 빈칸이 나오는 경우가 있어 조건을 추가했다

import math

def notation(n, q):
    rev_base = ''
    while n > 0:
        n, mod = divmod(n, q)
        rev_base += str(mod)

    return rev_base[::-1] 

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

def solution(n, k):
    answer = 0
    nums = (notation(n, k)).split("0")

    for num in nums:
        if num and prime(int(num)):
            answer += 1
    return answer