728x90
https://programmers.co.kr/learn/courses/30/lessons/92335
코딩테스트 연습 - k진수에서 소수 개수 구하기
문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소
programmers.co.kr
문제 풀이
import java.util.*;
public class Solution {
public int solution(int n, int k) {
String str;
if (k == 10)
str = String.valueOf(n);
else {
StringBuilder sb = new StringBuilder();
int r; // remainder
while (n > 0) {
r = n % k;
r += r < 10 ? '0' : 'A' - 10;
sb.insert(0, (char) r);
n /= k;
}
str = sb.toString();
}
StringTokenizer st = new StringTokenizer(str, "0");
int answer = 0, m, i; long num;
loop:
while (st.hasMoreTokens()) {
num = Long.parseLong(st.nextToken());
if (num < 2) continue;
m = (int) Math.sqrt(num);
for (i = 2; i <= m; i++)
if (num % i == 0)
continue loop;
answer++;
}
return answer;
}
}
- k (진수) 가 10이 아닌 경우, k 진법으로 변환 ( String )
- 문제에 제시 된 조건을 보면 0을 포함하지 않는 수를 의미한다.
즉, 0을 구분자로 하여 얻을 수 있는 수들 중 소수의 개수를 구해야 한다.
- StringTokenizrer 를 이용하여 구분자를 "0" 으로 하고
토큰마다 숫자 형식으로 변환 후
그 수가 소수인지 판단하여 개수를 카운트 하면 됨
반응형