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

💡 풀이

• k진수로 변환할 때 나눈 나머지를 StringBuilder에 저장하고 마지막에 문자열을 뒤집어서 진수로 변환
• 진수로 바꾼 숫자를 0을 기준으로 분리
• 분리해서 각 숫자가 소수인지 판별
• 🚨 주의 -> 시간초과 발생
  • long 자료형 필요 -> n의 최대값인 1,000,000을 2진수로 변환하면 2^19로 19자리쯤 되는 10진수로 변환됨
  • 소수 판별할 때 n의 제곱근보다 작은 자연수로 확인하기 -> 0 기준으로 분리했을 때 특정 값이 "1122222222221" 이렇게 크다면 n보다 작은 수로 반복문 돌면서 확인하면 너무 오래걸림

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        String num = calNum(n, k); // 진수 계산
        String[] splitNum = num.split("0"); // 0을 기준으로 분리하기
        for(String s : splitNum){
            if (s.isEmpty()) continue;
            if (isPrime(Long.parseLong(s))) answer++;
        }
        
        return answer;
    }
    
    // k진수로 변환
    public String calNum(int num, int k){
        StringBuilder sb = new StringBuilder();
        
        while(num >= k){
            long n = num % k;
            sb.append(String.valueOf(n));
            num /= k;
        }
        sb.append(num);
        return sb.reverse().toString();
    }
    
    // 소수 판별
    public boolean isPrime(long num){
        if (num <= 1) return false;
        for(int i = 2; i<=Math.sqrt(num); i++){
            if (num % i == 0) return false;
        }
        return true;
    }
}