[카카오 코테 2022 | python] k진수에서 소수 개수 구하기

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92335
• level2
• 2022 KAKAO BLIND RECRUITMENT

 

Q1) 문제를 어떻게 이해하셨나요?
A1) 이 문제는 양의 정수 n을 k진수로 바꾼 후, 그 안에 0을 기준으로 나뉜 연속된 숫자들 중 소수인 수의 개수를 구하는 문제입니다. 여기서 주의할 점은, 진수 변환 이후0으로 둘러싸이거나 경계에 있는 숫자들을 소수 후보로 보고, 10진수로 해석해서 소수인지 판단해야 한다는 점입니다.

Q2) 풀이 계획
A2) 먼저 n을 k진수 문자열로 변환합니다. 변환된 문자열을 '0'을 기준으로 분할합니다. 각 토큰에 대해 비어 있지 않고 10진수로 변환했을 때 소수이면 결과에 포함시킵니다. 최종적으로 소수 개수를 리턴합니다.

 

💡 최적화된 코드

# k진수는 숫자를 k개의 숫자(기호)를 사용해 표현하는 방식
def to_k_base(n, k):
    result = ''
    while n > 0:
        result = str(n % k) + result
        n //= k
    return result

# 소수는 1과 자기 자신만을 약수로 가지는 자연수
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1): # √n까지만 확인
        if n % i == 0:
            return False
    return True

def solution(n, k):
    k_base = to_k_base(n, k)
    parts = k_base.split('0')
    
    result = 0
    for p in parts:
        if p == '':
            continue
        if is_prime(int(p)):
            result += 1
    return result