[프로그래머스] k진수에서 소수 개수 구하기 (Python)

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

프로그래머스 k진수에서 소수 개수 구하기 문제 설명

프로그래머스 k진수에서 소수 개수 구하기 제한사항 및 입출력 예시

---

• 2022 KAKAO BLIND RECUITMENT 분류 문제이며 프로그래머스 LEVEL 2 난이도의 문제다
• 문제 난이도 자체는 어렵지 않으나 N진수 변환, 소수 판별 등 기본기가 중요한 문제다
• 문제 조건에 따르면 P는 0사이 또는 0의 좌, 우에 위치하므로 split()을 이용하면 각 P를 구할 수 있다
• 따라서 순서대로 입력 받은 n을 k진수로 변환 후, split("0")로 숫자를 받아서 소수인지 판별해주면 된다 

 

k진수 변환

10진수를 k진수로 변환하는 방법은 n에서 k로 나눈 나머지를 역순으로 바꾸면 된다

def k_num(n,k):
    #10진수의 경우 변환할 필요가 없으므로 바로 return 해준다
    if k == 10:
        return n
    else:
        new_n = ""
        while n > 0:
            new_n += str(n % k)
            n = n // k
        return new_n[::-1]

 

 

소수 판별

소수는 1과 n 이외의 숫자로 나눠지지 않으므로, 2부터 n의 루트까지 한 번이라도 나누어 떨어질 때 False를 return 한다
* 참고로 1은 소수가 아니므로 1보다 작을 경우 역시 False를 return 한다

def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**(1/2)+1)):
        if n % i == 0:
            return False
    return True

 

전체 코드

따라서 전체 코드는 아래와 같다

def k_num(n,k):
    if k == 10:
        return n
    else:
        new_n = ""
        while n > 0:
            new_n += str(n % k)
            n = n // k
        return new_n[::-1]

def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**(1/2)+1)):
        if n % i == 0:
            return False
    return True
    
def solution(n, k):
    answer = 0
    num = k_num(n,k)
    nums = str(num).split("0")
    for x in nums:
    	#x가 비어있는 경우를 예외처리 한다
        if x and isPrime(int(x)):
            answer += 1
    return answer

 

GitHub에서 코드 보기