[프로그래머스] k진수에서 소수 개수 구하기

코드 힌트

1. 진법 변환:
   • 주어진 수를 k진법으로 변환해야 합니다. 변환 과정에서는 n을 k로 나눈 나머지를 문자열에 계속 추가하고, n을 k로 나누는 과정을 반복합니다. n이 k보다 작아지면 마지막 몫을 추가하고, 최종 문자열을 reverse하여 반환합니다.
2. 조건에 맞는 소수 찾기:
   • 문제의 핵심은 진법 변환 후 나온 숫자들 중에서 소수를 찾는 것입니다. 이를 위해 변환된 문자열을 '0'을 기준으로 split() 하여 숫자 배열로 나눈 다음, 각 숫자가 소수인지 확인해야 합니다.
3. 소수 판별:
   • 각 숫자가 소수인지 확인하는 방법은 간단합니다. 숫자 1은 소수가 아니므로 바로 제외하고, 2부터 해당 숫자의 제곱근까지의 수로 나누어지지 않는지 확인합니다. 나누어지는 숫자가 없으면 소수입니다.
4. 진법 변환 후 소수 개수 계산:
   • 입력된 숫자를 k진법으로 변환한 후, 이를 '0'을 기준으로 split() 합니다. 그런 다음, 배열의 각 요소를 순회하며, 빈 문자열이 아니고 소수인 경우, 결과 값에 1을 더합니다. 최종적으로 소수의 개수를 반환합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int result = 0;
        
        // 숫자 n을 k진법으로 변환하여 문자열로 얻습니다.
        String num = convertToBase(n, k);
        
        // 진법 변환 후 0을 기준으로 숫자를 나눕니다.
        String[] arr = num.split("0");
        
        // 나누어진 각 숫자가 소수인지 확인합니다.
        for (String s : arr) {
            if (!s.isBlank() && isPrimeNumber(Long.parseLong(s))) {
                result++;
            }
        }
        return result;
    }
    
    // 주어진 숫자가 소수인지 판별하는 메서드입니다.
    public boolean isPrimeNumber(long num) {
        if (num == 1) return false; // 1은 소수가 아님
        for (int i = 2; i <= (int)Math.sqrt(num) + 1; i++) {
            if (num % i == 0) {
                return false; // 나누어 떨어지는 경우 소수가 아님
            }
        }
        return true; // 소수인 경우
    }
    
    // 숫자 n을 k진법으로 변환하는 메서드입니다.
    public String convertToBase(int n, int k) {
        StringBuilder sb = new StringBuilder();
        
        if (n < k) {
            return "" + n; // n이 k보다 작으면 변환 없이 그대로 반환
        }
        
        while (n >= k) {
            sb.append(n % k); // 나머지를 구해서 추가
            n /= k; // n을 k로 나눔
        }
        sb.append(n); // 마지막 몫 추가
        
        return sb.reverse().toString(); // 뒤집어서 반환
    }
}