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

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

💡 문제

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

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

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

⚠️ 제한사항

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

✅ 풀이

👆 첫 번째 풀이 (실패)

최근에 탐색 문제를 풀었더니 약수가 너무 반가웠다. 제한사항에 n이 분명히 크다고 나와있고, 길다고 나와있어서 제곱근까지.. 하려다가 그냥 유턴해서 수의 절반까지만 구하기로 했다.

그런데 보기 좋게 실패했다. 문제점은 숫자가 길 경우, Int형으로 처리가 되지 않아서이다.

class Solution {
    fun checkIsPrime(n: String): Boolean {
    	// Long으로만 바꾸면 되겠지? ㅎㅅㅎ
        val num = n.toInt()
        return num != 1 && (2..num/2).all { num % it != 0 }
    }
    
    fun solution(n: Int, k: Int): Int {
        val numbers = n.toString(k).split('0')
        
        return numbers.count { 
            it.isNotBlank() && checkIsPrime(it) 
        }
    }
}

✌️ 두 번째 풀이 (실패)

Long으로 바꿔서 풀었지만, 시간 초과가 발생했다. 아무래도 약수를 구하는 데 시간이 오래 걸리는 것 같아서 제곱근까지 구하기로 했다.

class Solution {
    fun checkIsPrime(n: String): Boolean {
        val num = n.toLong()
        return num != 1L && (2..num/2).all { num % it != 0L }
    }
    
    fun solution(n: Int, k: Int): Int {
        val numbers = n.toString(k).split('0')
        
        return numbers.count { 
            it.isNotBlank() && checkIsPrime(it) 
        }
    }
}

👌 세 번째 풀이 (성공)

실패는 여러번 했지만, 문제점은 금방금방 해결할 수 있어서 다행이었다.

import kotlin.math.sqrt
 
class Solution {
    fun checkIsPrime(n: String): Boolean {
        val num = n.toLong()
        val sq = sqrt(n.toDouble()).toLong()
        return num != 1L && (2..sq).all { num % it != 0L }
    }
    
    fun solution(n: Int, k: Int): Int {
        val numbers = n.toString(k).split('0').filter(String::isNotBlank)
        
        return numbers.count { checkIsPrime(it) }
    }
}

🔥 다른 사람의 풀이

다른 사람 풀이들을 보다 신기한 걸 확인했다. 자바에 소수일 수 있는 확률..?을 알려주는 isProbablePrime이란 게 있다고 한다. 왜 확률이냐! 바로 BigInt의 함수라 큰 수도 소수인지 알려주기 때문이다. 그래서 인자로 certainty를 전달해줘야 하는데, 역할은 대충 다음과 같다.

For certainty = 1 ==> required probability = 1-(0.5)^1 = 1–0.5 = 0.5 (or 50%)
For certainty = 2 ==> required probability = 1-(0.5)^2 = 1–0.25 =0.75 (or 75%)
For certainty = 3 ==> required probability = 1-(0.5)^3 = 1–0.125 = 0.875 (or 87.25%)

import java.math.*
class Solution {
    fun solution(n: Int, k: Int): Int {
        var answer: Int =0
        val newN = n.toString(k).split("0")
        for(i in newN) {
            if(i == "" || i == "0" || i == "1") continue
            if(BigInteger(i).isProbablePrime(1)) answer ++
        }
        return answer
    }
}

자바는 정말.. 알아도 알아도 끝이 없는 것 같다.

💭 후기

정확성을 전달해서 소수일 수 있는 확률을 알 수 있다는 게 너무 신기했다. 매일 새로운 걸 알아가는 것 같다.