2022 KAKAO BLIND RECRUITMENT k진수에서 소수 개수 구하기 Lv. 2

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92335

파이썬 소스: https://bit.ly/3xJfKAZ

 

문제는 크게 2가지 부분으로 나눌 수 있습니다.

1. 정수를 k진법으로 변환하기

2. 어떤 숫자가 소수인지 판별하기

1번 진법 변환하는 부분부터 코딩해보겠습니다.

def jinbum(n, k):     if n == 0:         return ''     return jinbum(n // k, k) + str(n % k)

정수 n, k는 solution의 인자로 주어지는 n, k입니다. 진법변환은 재귀적으로 호출되며, 나눈 몫이 0이 될 때까지 재귀호출 합니다. 나눈 몫은 0보다 크다면, 다시 진법변환함수에 인자로 주고, 나머지는 스트링으로 변환해서, 결과의 오른쪽에 붙여 줍니다.

 

어떤 숫자 v가 소수인지 판단하려면, 2 부터 루트v +1까지 모든 숫자로 v를 나눠서 모두 나머지가 0이면, 숫자 v는 소수입니다.

def is_prime(v: int) -> bool:     for n in range(2, int(sqrt(v)) + 1):         if 0 == v % n:             return False     return True

루트v는 sqrt()함수를 사용해서 구합니다. 1인 경우도 False로 리턴해야 하지만, 다른 부분에서 처리해서, is_prime()에는 2이상의 숫자만 입력으로 들어오게 합니다.

 

def solution(n, k):     answer = 0     vs = jinbum(n, k)     for v in vs.split('0'):         if v == '' or v == '1':             continue         if is_prime(int(v)):             answer += 1     return answer

함수 jinbum()을 호출해서, n숫자를 k진법의 스트링으로 변환합니다.

문제에서는 0P0, P0, 0P 등으로 길게 설명하고 있지만, split(‘0’)을 하면 해당 설명에 모두 만족하는 스트링과 ‘’ 스트링이 만들어 집니다.

‘’ 스트링과, ‘1’ 인 경우는 제외합니다.

함수 is_prime()을 호출해서 v가 소수인지 확인하고, answer에 1을 증가시키면 문제를 풀 수 있습니다.

 

궁금한 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래에 있습니다.

from math import sqrt def solution(n, k):     answer = 0     vs = jinbum(n, k)     for v in vs.split('0'):         if v == '' or v == '1':             continue         if is_prime(int(v)):             answer += 1     return answer def jinbum(n, k):     if n == 0:         return ''     return jinbum(n // k, k) + str(n % k) def is_prime(v: int) -> bool:     for n in range(2, int(sqrt(v)) + 1):         if 0 == v % n:             return False     return True