k진수에서 소수 개수 구하기

 

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

 

문제가 다소 복잡해 보이지만, 결국 n을 k진수로 바꾼 뒤 0을 기준으로 쪼갠 숫자들이 0이 포함되지 않은 소수인가, 를 묻는 문제이다.

 

이때, 쪼개진 숫자들이 정수의 범위를 넘어설 수 있기때문에 Long 으로 체크를 해야한다.

 

테스트 케이스 1, 14, 15에서 계속 통과하지 못해서 한참 고민했다.

 

처음엔 n 까지의 소수를 모두 구해놓고 시작했다.

 

혹시나 해서, 쪼갠 숫자들이 소수인지 체크하는 방식으로 변경했더니 통과되었다.

 

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        
        int count = 0;
        String[] nums = Integer.toString(n, k).split("0");
        for (String num : nums) {
            if (num.length() < 1) continue;
            if (isPrime(Long.parseLong(num))) count++;
        }
        
        return count;
        
    }
    
    boolean isPrime(long n) {
        if(n == 1)  return false;
        
        long a = (long) Math.sqrt(n) + 1L;
        for(int i = 2; i < a; i++) {
            if(n % i == 0) return false;
        }
        
        return true;
    }
}