[코딩테스트] 프로그래머스 k진수에서 소수 개수 구하기 파이썬(Python)

 

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

import math
def solution(n, k):
    
    result = 0
    k_number = k_change(n, k)
    numbers = k_number.split('0')
    for number in numbers:
        if number == '':
            pass
        else:
            if is_prime(int(number)):
                result +=1
    return result

def k_change(n, k):
    result = ''
    while n:
        result += str(n % k)
        n = n // k
    return result[::-1]

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

문제는 해결하였지만 궁금했던 점은 split('0')을 하였을 때 5가지의 모든 조건을 만족했다는 것입니다.

 

개인적인 생각으로는 

437674의 값은 3진수로 표현하면 211020101011이 됩니다.

'0'을 기준으로 split을 적용하면 [211, 2, 1, 1, 11]이 됩니다.

위의 리스트를 소수판별을 하면 [211, 2, 11]이 소수이기 때문에 결과는 3으로 정답이 됩니다.

중간에 있는 101의 값은 [1,1]로 분리가 되면서 자연스럽게 소수로 판별하지 않고 무시가됩니다.

이러한 이유로 5번째 조건이 자연스럽게 통과가 되는 것이 아닐까 라는 생각이듭니다.

같은 이유로 n = 101, k=10일때에도 101의 값은 P조건에 부합하지 않아서 결과값 0이됩니다.

값은 [1,1]로 분리가되어 자연스럽게 0의 결과가 나오는 것을 확인할 수 있습니다.

 

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

카카오의 해설을 확인해보았을 때

이 문제는 진법 변환 후에 변환된 숫자를 0을 기준으로 파싱하고, 파싱 한 숫자를 소수 판별해 해결할 수 있는 문제입니다.

라는 문구를 보았을 때 0을 기준으로 파싱만 할 수 있다면 풀 수 있는 중요한 조건이 아닌 것 같습니다..

 

저는 문제에서 요구한대로 k진수를 구하고 소수인지 판별하는 코드를 작성하였습니다.

def k_change(n, k):
    result = ''
    while n:
        result += str(n % k)
        n = n // k
    return result[::-1]

위와 같은 함수를 작성하여 k진수로 변경하는 작업을 진행 한뒤에

numbers = k_number.split('0')

'0'을 기준으로 나누어 주고 소수판별을 진행했습니다.

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

모든 값을 확인하면 테스트케이스에서 시간초과가 나기 때문에 i를 2부터 주어진 number의 제곱근까지 확인하는 것으로 시간을 줄여서 해결하였습니다.

해설 처럼 에라토스테네스의 체를 이용한 방법도 존재하지만 저는 약수의 성질을 이용하여 해결하였습니다.