프로그래머스 - 92335번: k진수에서 소수 개수 구하기 [Java]

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

프로그래머스

1. 코드

import java.math.*;
class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        StringBuilder sb = new StringBuilder();
        while(n > 0) {
            sb.append(n % k);
            n /= k;
        }
        
        for(String s : sb.reverse().toString().split("0")) {
            if(s.isEmpty()) continue;
            BigInteger num = new BigInteger(s);
            if(num.isProbablePrime(5))
                answer++;
        }
        return answer;
    }
}

2. 설명

int answer = 0;
StringBuilder sb = new StringBuilder();
while(n > 0) {
    sb.append(n % k);
    n /= k;
}

반복문을 통해서 n을 k진수로 변환합니다. StringBuilder에는 변환된 진수가 거꾸로 저장이 될 것입니다.

for(String s : sb.reverse().toString().split("0")) {
    if(s.isEmpty()) continue;
    BigInteger num = new BigInteger(s);
    if(num.isProbablePrime(5))
        answer++;
}

따라서 거꾸로 저장되었기에 그것을 StringBuilder.reverse()를 통해 반전시켜 주며 0을 기준으로 분리해 줍니다. 빈칸이 존재할 수도 있기에 빈칸일 경우 제외하여 BigInteger.isProbablePrime()을 통해서 소수를 판별하여 소수라면 answer에서 1 증가해 줍니다.

3. 정리

1. BigInteger.isProbablePrime()을 통해서 쉽게 소수 판별이 가능하며 Parameter는 반복 횟수이며 확률적으로 소수를 판별하기에 최소 5 이상을 권장합니다.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges