컴퓨터/프로그래머스
프로그래머스 - 92335번: k진수에서 소수 개수 구하기 [Java]
이상한 나그네
2023. 10. 23. 00:48
문제: 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. 정리
- BigInteger.isProbablePrime()을 통해서 쉽게 소수 판별이 가능하며 Parameter는 반복 횟수이며 확률적으로 소수를 판별하기에 최소 5 이상을 권장합니다.
출처: 프로그래머스 코딩 테스트 연습,
https://school.programmers.co.kr/learn/challenges