[카카오] k진수에서 소수 개수 구하기

문제 이해하기

양의 정수 n을 k진수로 변환한 후, 다음의 네 가지 규칙에 맞는 소수를 찾는 문제입니다.

• 0P0 형태의 소수: 양쪽에 0이 있는 소수
• P0 형태의 소수: 오른쪽에만 0이 있는 소수
• 0P 형태의 소수: 왼쪽에만 0이 있는 소수
• P 형태의 소수: 양쪽에 0이 없는 소수

예를들면 437674이라는 십지수 정수를 3진수로 변환하면 "211020101011"이 됩니다.

이 숫자들 중에 규칙이 적용되는 숫자를 찾으면 2110(P0 조건) 011(0P 조건), 020(0P0 조건)이 있어 답이 3이 됩니다.

문제 해결 방법 설명하기

1. 10진수를 k진수로 변환할 수 있어야합니다.

 

10진수에서 n을 k 진수로 변환하는 방법은 아래와 같습니다. 

1. n을 k로 나눈 몫과 나머지를 구합니다.
2. 해당 나머지를 가장 오른쪽 자리에 기록합니다
3. n이 0이될 때까지 1,2번의 작업을 반복합니다.
4. n이 0이되면 기록한 값을 뒤집으면 k진수를 얻을 수 있습니다

2. 주어진 10진수가 소수인지 판별이 가능해야 합니다.

 

소수의 정의는 1과 자기 자신 이외의 다른 자연수로는 나누어 떨어지지 않는 수를 의미합니다.

따라서 주어진 n이 있다면 1이외의 약수를 찾으면 됩니다.

 

3. 문자열에 주어진 조건에 맞는 부분 문자열을 반환할 수 있어야 합니다.

0을 기준으로 스플릿하면 위에서 언급한 네 가지 기준을 모두 만족할 수 있습니다. P0의 경우는 문자열을 0을 기준으로 스플릿한다면 맨 앞에 오는 부분 문자열과 일치합니다.

0P0의 경우는 0P의 조건에서 0이 추가된 것입니다. 즉, 0을 기준으로 스플릿한 중간 단계로 볼 수 있습니다.

0P의 경우는 스플릿에서 가장 마지막에 오는 부분 문자열입니다.

마지막으로, 0이 없는 경우에는 문자열 자체가 P가 됩니다.

 

예를들면 211020101011의 x진수가 존재하고, 0을 기준으로 split을 한다면 211, 0, 2, 0 ,1, 0, 0,11이 됩니다.

따라서 아래의 코드를 실행했다고 가정한다면, 211은 ,P0의 경우 2, 1은 0P0의 경우 11은 0P의 경우입니다.

    for i in k_binary.split('0'):
        if not i:
            continue
        
        if is_prime_num(int(i)):
            answer += 1

코드

import string
import math

def is_prime_num(n):
    if n <= 1:
        return False

    for i in range(2, int(math.sqrt(n))+1): # n의 제곱근을 정수화 시켜준 후 + 1
        if n % i == 0:
            return False

    return True

def convert(num, base) :
    tmp = string.digits+string.ascii_lowercase
    q, r = divmod(num, base)
    if q == 0 :
        return tmp[r] 
    else :
        return convert(q, base) + tmp[r]

def solution(n, k):
    answer = 0
    k_binary = convert(n, k)
    
    for i in k_binary.split('0'):
        if not i:
            continue
        
        if is_prime_num(int(i)):
            answer += 1

    return answer


if __name__ == "__main__":
    print(solution(2, 3))
    print(is_prime_num(1))

 

배운점 정리하기

0을 기준으로 스플릿한다는 것은 굉장히 혁신적인 방법이었다. 주어진 조건을 모두 만족하면서 굉장히 깔끔한 코딩을 했다. 위 코드는 바킹독님 풀이를 재작성한 것이다;.