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

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

 

문제

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

 

- 0P0처럼 소수 양쪽에 0이 있는 경우

- P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우

- 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우

- P처럼 소수 양쪽에 아무것도 없는 경우

- 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.

 

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는

소수의 개수를 return하도록 solution 함수를 완성해 주세요.

 

풀이

먼저 이 문제에서 반드시 필요한 해당 숫자가 소수인지 판단한는 함수를 작성해보겠습니다.

def checkPrime(num):
	if num < 2: return False
    
    for i in range(2, int(math.sqrt(num))+1):
    	if num i % i == 0:
        	return False
    return True

그럼 이번에는 조건을 만족하는 수를 구해보도록 하겠습니다.😆

문제에서 보면 알 수 있듯이 0을 기준으로 숫자가 결정되는 것을 알 수 있습니다.

 

따라서 k진수의 수로 바꿀 때 나머지가 0이 되는 시점을 기준으로 이전에 나온 수가

조건을 만족하는 숫자 입니다. 이를 코드로 바꾸면 아래와 같습니다.

num, pos = 0 # 조건을 만족하는 수, 10단위 수
while n > 0:
	mod = n % k
    
    if mod == 0:
    	# 이전까지의 수가 조건을 만족하는 수 = num
        # 소수인지 검사하는 로직 필요
        num, pos = 0, 0
    else:
    	num += mod * math.pow(10, pos)
        pos += 1
    
    n //= k

 

코드

Python 풀이

import math
def solution(n, k):
    num, pos, answer = 0, 0, 0
    
    while n > 0:
        mod = n % k
        
        if mod == 0:
            if checkPrime(num):
                answer += 1
            num, pos = 0, 0
        else:
            num += mod * math.pow(10, pos)
            pos += 1
        
        n //= k
    
    if num != 0 and checkPrime(num):
        answer += 1
    
    return answer

def checkPrime(num):
    if num < 2: return False

    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

Kotlin

🌹 자료형에 주의해야 합니다.😭

import kotlin.math.*

class Solution {
    fun solution(n: Int, k: Int): Int {
        var num = n.toLong()
        var no = 0L
        var pos = 0
        var answer = 0
        
        while (num > 0L) {
            val mod = num % k
            
            if (mod == 0L) {
                if (checkPrime(no)) {
                    answer += 1
                }
                no = 0
                pos = 0
            } else {
                no += (mod * (10.0).pow(pos).toLong())
                pos += 1
            }
            
            num = (num/k).toLong()
        }
        
        if (checkPrime(no)) {
            answer += 1
        }
        
        return answer
    }
    
    fun checkPrime(num: Long): Boolean {
        if (num < 2) return false
        
        for (i in 2..sqrt(num.toDouble()).toInt()) {
            if (num % i == 0L) {
                return false
            }
        }
        return true
    }
}