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

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

프로그래머스

트러블 슈팅

런타임 에러

 1 <= n <= 1000000 이므로, n이 1000000일 때, 2진법으로 11110100001001000000이고 이를 표기하는데 int가 부족해서 발생한 이슈 였다. k진법으로 변경된 n의 타입을 long으로 변경 했더니 런타임 에러가 사라졌다.

 

시간 초과

테스트 케이스 1번에서 시간 초과가 발생했다. 소수 여부 판별 코드에서 별 생각 없이

for (int i = 2; i <= n/2; i++) {

 

로 했었는데, 이것 때문에 발생한 이슈였다. 받은 숫자의 제곱근까지만 반복해줘도 소수 판별이 가능하다고 한다.

for (int i = 2; i <= Math.sqrt(n); i++) {

 

로 수정하니 이슈가 사라졌다.

 

작성한 코드

class Solution {
    public int solution(int n, int k) {
        int answer = 0;        
        
        // k 진법으로 바꾸기
        StringBuilder builder = new StringBuilder();
        int quotient = 0; // 몫
        int remainder = 0; // 나머지       
        while(n != 0) {
            quotient = n / k;
            remainder = n % k;
            builder.insert(0,remainder);
            n = quotient;
        }
        String changedString = builder.toString();

        // P 찾기
        if (!changedString.contains("0")) {
            
             if (changedString.isEmpty())
                return 0;

            if (isPrime(Long.parseLong(changedString)))
                return 1 ;
        }
        
        // P0, 0P0, 0P 찾기
        String[] splitedString = changedString.split("0");
        
        for (int i = 0; i < splitedString.length; i++) {
            
           if (splitedString[i].isEmpty()) continue;

           if (isPrime(Long.parseLong(splitedString[i]))
                    && !(i == splitedString.length - 1 && changedString.charAt(changedString.length() - 1) == '0')) {

                answer ++;
            }
        }
        return answer;
    }

    public static boolean isPrime (long n) {

        if (n < 2) return false;

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }

        return true;
    }
}