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

문제 링크

핵심

문제에 언급된 규칙들이 결국 k진법으로 변환시킨 수를 0단위로 split한 뒤 소수 인지를 파악해야 한다는 뜻이였음을 알아차리는 것이 중요한 문제였다.

코드

import java.util.*;

class Solution {
    
    static String convert(int n, int k) {
        String s = "";
        
        while(n>0) {
            s = n%k + s;
            n /= k;
        }
        
        return s;
    }
    
    static boolean check(long n) {
        if(n==1) return false;
        for(int i=2; i<=Math.sqrt(n); i++) {
            if(n%i==0) return false;
        }
        return true;
    }
    
    public int solution(int n, int k) {
        int answer = 0;
        
        String[] s = convert(n,k).split("0");
        
        for(int i=0; i<s.length; i++) {
            System.out.println(s[i]);
            if(s[i].length()!=0 && check(Long.parseLong(s[i]))) answer++;
        }
        
        return answer;
    }
}

소수 문제임을 보자마자 습관적으로 에라토스테네스의 체 를 활용해서 풀려고 했으나 n이 커질수록 long타입을 초과하는 길이의 소수가 나와 런타임 에러가 발생해 숫자마다 일일이 소수인지 체크해주는 방법으로 변경했다.