[Programmers] k진수에서 소수 개수 구하기(Python 풀이) - 2022 KAKAO BLIND RECRUITMENT

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

코딩테스트 연습 - k진수에서 소수 개수 구하기

풀이

1. k진수로의 변환

def to_k_number(n, k):  # n을 k진수로 반환
    ret = ""
    while n > 0:
        ret += str(n % k)
        n = n //  k
    return ''.join(reversed(ret))

2. 특정 소수 찾기

def is_prime_num(k):
    if k == 2 or k == 3: return True  # 2 or 3 은 소수
    if k % 2 == 0 or k < 2: return False  # 2의 배수이거나 2보다 작은 값인 경우 소수가 아님
    # 3부터 root(k)까지 2씩 증가하며 확인(3, 5, 7...),
    # 이는 작은 값들의 배수일 때 발생하는 중복을 제거하며 확인(소수 찾기 최적화)
    for i in range(3, int(k ** 0.5) + 1, 2):
        if k % i == 0:
            return False
    return True
 
 
def solution(n, k):
    answer = 0
    k_num = to_k_number(n, k)  # k진수로 반환
 
    # k_num을 0을 기준으로 분할하여 n을 가져옴
    for n in k_num.split('0'):
        if n == "": continue
        if is_prime_num(int(n)):  # n이 소수인 경우 answer+=1
            answer += 1
    return answer

is_prime_num()은 입력 숫자 k가 소수인지 확인하는 함수입니다. 모든 경우를 다 확인할 수 있지만, 빠른 실행을 위해 중복을 제거하여 확인하는 방식으로 소수를 판별하였습니다.
그리고 소수인지 판별하는 조건은 다음과 같은데

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.

이는 k진법으로 변환된 숫자를 문자열 변환한 후 0을 기준으로 분할하여 각 숫자를 10진수라고 가정하여 소수인지 판별하면 해결할 수 있습니다.
예를들어 n=4376741, k=3인 경우 k진수는 211020101011입니다.
이를 문자열로 변환한 후 0을 기준으로 분할하게되면 다음과 같습니다.

"211020101011".split('0')
['211', '2', '1', '1', '11']

전체 소스 코드

def to_k_number(n, k):  # n을 k진수로 반환
    ret = ""
    while n > 0:
        ret += str(n % k)
        n = n //  k
    return ''.join(reversed(ret))
 
 
def is_prime_num(k):
    if k == 2 or k == 3: return True  # 2 or 3 은 소수
    if k % 2 == 0 or k < 2: return False  # 2의 배수이거나 2보다 작은 값인 경우 소수가 아님
    # 3부터 root(k)까지 2씩 증가하며 확인(3, 5, 7...),
    # 이는 작은 값들의 배수일 때 발생하는 중복을 제거하며 확인(소수 찾기 최적화)
    for i in range(3, int(k ** 0.5) + 1, 2):
        if k % i == 0:
            return False
    return True
 
 
def solution(n, k):
    answer = 0
    k_num = to_k_number(n, k)  # k진수로 반환
    # k_num을 0을 기준으로 분할하여 n을 가져옴
    for n in k_num.split('0'):
        if n == "": continue
        if is_prime_num(int(n)):  # n이 소수인 경우 answer+=1
            answer += 1
    return answer

 

제출 결과