안녕하세요. 오늘은 프로그래머스의 k진수에서 소수 개수 구하기
문제를 풀어보겠습니다. 이 문제는 2022년도 KAKAO BLIND RECRUITMENT에서 출제되었습니다.
https://programmers.co.kr/learn/courses/30/lessons/92335
주어진 n을 k진수로 변환합니다.(변환하는 함수 convertNumber) k진수로 변환한 후, 문제 풀이의 편의성을 위해 해당 숫자를 String으로 치환해서 return합니다.
n을 k진수로 바꾼 String을 "0"으로 split합니다. String을 일일이 돌면서 "0"을 체크하기보다, 그냥 split하면 시간을 훨씬 많이 단축할 수 있습니다.
split한 값들은 String 배열에 담깁니다. 해당 배열을 돌면서 배열 속 숫자의 소수 여부를 확인합니다. 이 때, 2부터 소수의 제곱근까지만 확인해보면 소수 여부를 알 수 있습니다.
class Solution {
public int solution(int n, int k) {
int answer = 0;
String convertedNum = convertNumber(n, k);
String[] splitedNum = convertedNum.split("0");
for (String str : splitedNum) {
if ("".equals(str)) {
continue;
}
if(isSosu(Long.parseLong(str))) {
answer++;
}
}
return answer;
}
private boolean isSosu(long num) {
if(num == 1) return false;
int limit = 2;
while (limit <= Math.sqrt(num)) {
if(num % limit == 0) {
return false;
}
else {
limit ++;
}
}
return true;
}
private String convertNumber(int n, int k) {
if(k == 10) return Integer.toString(n);
StringBuilder sb = new StringBuilder();
while (n > 0) {
sb.append(n % k);
n /= k;
}
return sb.reverse().toString();
}
}
처음에 제출했을 때 1번 테스트 케이스가 시간초과 나고 11번 테스트 케이스가 틀렸습니다. 문제는 두 가지였습니다.
초기에는 소수 판별 로직의 while문 범위를 2부터 n/2까지로 잡았습니다. 그랬더니 1번 테스트케이스에서 시간초과가 났습니다. 답 확인 결과 n의 제곱근까지만 범위를 잡아도 소수를 판별할 수 있었습니다.
초기에는 n을 k진수로 변환한 결과값의 자릿수를 for문을 돌면서 한 자리씩 탐색했습니다. 답을 확인해보니 매우 비효율적인 풀이였고, 그냥 split을 쓰면 로직이 많이 단축될 수 있는 문제였습니다.