[Programmers] k진수에서 소수 개수 구하기 (Kotlin)

Yeon·2024년 1월 15일

kotlin programmers

Algorithm

목록 보기

3/3

[k진수에서 소수 개수 구하기]

Programmers k진수에서 소수 개수 구하기

문제 설명

양의 정수 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

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.

풀이

문제를 읽고 어떻게 코드를 작성할까 생각해보았다.

n을 k진수로 바꾼다.
k진수로 바꾼 숫자를 0을 기준으로 나눈다.
나뉜 숫자들이 소수인지 확인하여 카운트에 +1을 한다.

코드

1. 코드 1 (런타임 에러)

class Solution {
	fun toKBase(n: Int, k: Int): String {
    	// n을 k진수로 변환
        return n.toString(k)
    }
    
    fun isPrime(n: Int): Boolean {
    	// 2 미만의 수는 소수가 아님
        if (n < 2) return false
        
        // 2부터 제곱근까지의 수로 나누어 소수 여부 확인
        for (i in 2..Math.sqrt(n.toDouble()).toInt()) {
        	if (n % i == 0) return false
        }
        return true
    }
    
    fun countPrimes(n: Int, k: Int): Int {
    	val kBaseNum = toKBase(n, k)
        val segments = kBaseNum.split("0")
        
        return segments.count { it.isNotEmpty() && isPrime(it.toInt()) }
    }

	fun solution(n: Int, k: Int): String {
    	return countPrimes(n, k)
    }
}

위와 같이 코드를 작성했는데 테스트 케이스 1과 11에 런타임 에러가 발생했다.

코드를 살펴보았을 때 왠지 isPrime함수에서 런타임 에러가 발생하는 것 같은데 이유를 잘 모르겠어서 프로그래머스 코딩테스트 연습 힌트 모음집을 한 번 보았다.

isPrime은 k진수로 바꾼 수가 소수인지 판별하기 위한 함수이다.
2부터 제곱근까지만 나누기 때문에 이 코드는 잘 작성했다고 생각했는데 int만 사용해서 문제가 생긴 것 같다.

2. 코드 2 (isPrime 함수 매개변수 변경)

isPrime 함수의 매개변수를 Int가 아닌 Long으로 바꿔서 코드를 작성해보았다.

class Solution {
    fun toKBase(n: Int, k: Int): String {
        // n을 k진수로 변환
        return n.toString(k)
    }
    
    fun isPrime(n: Long): Boolean {
        // 2 미만의 수는 소수가 아님
        if (n < 2) return false
        
        // 2부터 제곱근까지의 수로 나누어 소수 여부 확인
        for (i in 2..Math.sqrt(n.toDouble()).toLong()) {
            if (n % i == 0L) return false
        }
        return true
    }
    
    fun countPrimes(n: Int, k: Int): Int {
        val kBaseNum = toKBase(n, k)
        val segments = kBaseNum.split("0")
        return segments.count { it.isNotEmpty() && isPrime(it.toLong()) }
    }
    
    fun solution(n: Int, k: Int): Int {
        return countPrimes(n, k)
    }
}

소수를 확인하는 동안 Int타입을 사용하면 큰 수의 경우 NumberFormatException이 발생할 수 있기 때문에 isPrime함수의 매개변수를 Long타입으로 변경하였다.
실행 결과는 아래와 같이 성공이다!
테스트 통과