프로그래머스: k진수에서 소수 개수 구하기 (파이썬, 구현)

간단한 구현 문제인데 구현할게 조금 있어서 30분보단 조금 더 걸렸던 문제였다.

 

문제를 풀기 위해서는 세가지를 구현해야 하는데 첫째로 10진수를 n진수로 변환해주는 함수, 두번째로 소수인지 아닌지 판단하는 함수, 마지막으로 n진수에서 0을 기준으로 숫자들을 나누는 함수이다.

 

함수는 순서대로 보겠다. 우선 소수인지 아닌지를 판단하는 함수이다. 프로그래머스를 좀 풀어본 사람이라면 알텐데 소수구하는 문제가 은근 많아 소수 구하는 방법은 외울 정도이다. 제곱근보다 작은 구간에서 약수를 가진다면 수를 그 약수로 나눈 수는 제곱근보다 큰 구간에서 약수가 되므로 제곱근까지만 약수가 있는지 없는지를 보면 된다.

 

다음으로 진법 변환 함수이다. 아마 컴퓨터공학이나 전자전기공학을 전공한 사람들은 다 알텐데 10진수를 n진수로 변환하려면 10진수를 n으로 나눈 값이 n보다 작을때까지 구하고, 나머지들을 합치면 그 합친 수가 변환한 수이다. n보다 작을 때까지 구하는건 n진수는 n-1까지 표현할 수 있기 때문이다.

 

혹시 모르는 사람들이 있을 수 있으니 테스트 케이스1을 3진수로 변환하는 것을 보인다.

Figure1. 테스트 케이스1 3진수 변환

 Figure1에서 보이듯이 변환하고자 하는 수를 몫이 3보다 작을 때까지 나눈 후, 3보다 작은 몫(2)와 나머지들을 더하면 3진수 변환한 수가 된다. 테스트 케이스1에서는 211020101011이 된다.

 

마지막으로 0을 기준으로 수를 계속 더하는 함수는 while문을 이중중첩하여 구현하면 된다.

 

아래는 내가 위 세가지 함수를 이용해 푼 코드이다.

def sosu(n):
    # 제곱근까지 약수가 없다면 소수, 하나라도 있다면 ~소수
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def convert(n, k):
    result = ''
    while n > k:
        # n의 몫이 k보다 작을때 까지 나누고, 나머지를 합치면 변환된 수
        a, b = divmod(n,k)
        result += str(b)
        n = a
    result += str(n)
    return result[::-1]


def solution(n, k):
    answer = 0
    result = convert(n,k)
    i = 0
    while i < len(result):
        cash = ''
        j = i
        while j < len(result) and result[j] != '0':
            cash += result[j]
            j += 1
        i = j
        i += 1
        if cash:
            if cash == '1':
                continue
            elif cash == '2':
                answer += 1
            else:
                if sosu(int(cash)):
                    answer += 1
    return answer