[프로그래머스] 2022 KAKAO BLIND RECRUITMENT k진수에서 소수 개수 구하기(python3)

📌문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

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

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

입출력 예

n	k	result
437674	3	3
110011	10	2

프로그래머스 2022 KAKAO BLIND RECRUITMENT k진수에서 소수 개수 구하기

💡Idea

👩‍🏫 문제 해결 순서

1. 숫자를 k진수로 변환한다.
2. 변환된 숫자에서 0P0, P0, 0P, P인 경우를 찾는다.
3. 찾은 각 숫자가 소수인지를 확인한다.
4. 소수의 개수를 return한다.

이 문제를 해결하기 위해서는 위와 같은 4단계를 거쳐야 합니다.

k진수 변환 같은 경우, 우리가 알고 있는 진수 변환의 방법을 그대로 구현하였고, 소수 확인의 경우, 확인하려는 수의 제곱근까지의 수 중 나누어떨어지는 수가 존재하는지를 확인하는 방식으로 구현하였습니다.

💻코드

import math

def convert_to_k(n, k): # n을 k진수로 변환한 값을 문자열의 형태로 return하는 함수
    k_int = [] # k진수 변환 숫자 리스트
    while n > 0:
        k_int.append(n % k) # n을 k로 나눈 나머지 리스트 추가
        n = n // k # n을 k로 나눈 몫
    k_int.reverse() # 리스트 뒤집기
    return ''.join(map(str, k_int)) # 리스트를 문자열 형태로 변환하여 return

def is_prime(k): # 소수인지 확인하는 함수
    for i in range(2, int(math.sqrt(k)) + 1): # 2부터 제곱근까지 확인
        if k % i == 0: # 나누어떨어지면 소수 아님
            return False
    return True # 나누어떨어지는 게 없으면 소수


def solution(n, k):
	# 10진수가 아니라면 k진수로 변환 후, 0으로 문자열 split -> P를 구할 수 있다
    k_int = (convert_to_k(n, k) if k != 10 else str(n)).split('0')
    ans = 0
    for k in map(int, list(filter(lambda x: x != '' and x != '1', k_int))):
        if is_prime(k): ans += 1 # 소수라면 정답 1 추가
    return ans