프로그래머스 - k진수에서 소수 개수 구하기

문제 설명

제한사항 및 입출력

풀이

카카오 문제답게 설명이 친절하다. 글이 많아 조금 복잡해보이지만 주어진 숫자 n을 k진수로 바꾸고 0으로 split한 후 나온 숫자들이 소수인지 판별하는 문제이다.

별다른 알고리즘이 있는 것 같지는 않고 그냥 구현 문제같다.

내 코드

def convert_to_k(n, k):
    if n == 0:
        return "0"
    
    ret = []
    while n > 0:
        ret.append(str(n % k))
        n //= k
        
    return "".join(reversed(ret))

def is_prime(x):
    if x < 2:
        return False
    
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
        
    return True

def solution(n, k):
    k_num = convert_to_k(n, k)
    
    # "", "1" 제거 후 int로 변환
    num = list(map(int, filter(lambda x: x not in ("", "1"), k_num.split("0"))))
    
    return sum(is_prime(i) for i in num)

n을 k진수로 변환한 수에서 0으로 split했을 때 나올 수 있는 수들을 각각 소수 판별하기 때문에

시간 복잡도는 O(n^0.5 * log_k(n)) 이다.