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

문제 풀이 방식

• K진수로 변환 -> 이를 반복문 돌면서 소수인지 검사하기
• 오버플로우가 발생할 수 있으니 Long으로 변환해야한다.
• Java에서는 Integer.toString(n, k) 메소드를 통해 간단히 k진수로 변환할 수 있다.

문제 풀이 (Java)

class Solution {
    public int solution(int n, int k) {
        String n_k = toKBinary(n, k);
        int res = 0;
        String[] checks = n_k.split("0");
        
        for(String check : checks){
            if(check.equals("")) continue; 
            // 공백일때는 체크 안하고 넘어감
            
            Long tmp = Long.parseLong(check);
            if(isPrime(tmp)){
                res++;
            }
        }
        return res;
    }
    
    // K진수 변환
    public String toKBinary(int n, int k) {
        String res = "";
        while(n > 0) {
            res = n % k + res;
            n /= k;
        }
        return res;
    }
    
    // 소수 여부를 판정
    public boolean isPrime (long a){
        if(a <= 1) return false;
        
        for(int i = 2;i <= Math.sqrt(a);i++){
            if(a % i == 0) return false;
            
        }
        
        return true;
    }
}