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

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

프로그래머스

---

문제 풀이

* 에라토스테네스의 체 이용

* N진법 구하기 이용

 

 

첫 풀이로 아래 코드를 제출했고 76.2점이 나왔다.

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        // N진법 구하기
        String temp = "";
        while(n != 0){          
            temp = n % k + temp;
            n /= k;
        }
        
        String[] arr = temp.split("0");
        for(int i=0; i<arr.length; i++) {
            String str = arr[i];
            if(!str.isEmpty()) {
                if(isPrime(Integer.parseInt(str))) {
                    answer += 1;
                }
            }
        }
        return answer;
    }
    
    // 소수 판별 함수 : 에라토스테네스의 체 이용
    private boolean isPrime(int num) {
        if(num < 2) {
            return false;
        }
        
        for(int i=2; i<Math.sqrt(num); i++) {
            if(num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

 

 

소수를 판별하는 부분에서 int의 범위를 넘을 수 있다고 생각하여 다음과 같이 Long형으로 변경해주었다.

테스트 케이스 14, 16번이 실패하여 89.3점이 나왔다.

 

 

원인은 소수를 판별하는 isPrime 함수 내에서, 다음과 같이 제곱근까지 구해줄 때 범위를 잘못 계산했기 때문이었다.

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        // N진법 구하기
        String temp = "";
        while(n != 0){          
            temp = n % k + temp;
            n /= k;
        }
        
        String[] arr = temp.split("0");
        for(int i=0; i<arr.length; i++) {
            String str = arr[i];
            if(!str.isEmpty()) {
                if(isPrime(Long.parseLong(str))) {
                    answer += 1;
                }
            }
        }
        return answer;
    }
    
    // 소수 판별 함수 : 에라토스테네스의 체 이용
    private boolean isPrime(Long num) {
        if(num < 2) {
            return false;
        }
        
        // Math.sqrt() : 제곱근 함수
        // 제곱근을 씌운 값까지 포함해야 함!!!
        // ex) num이 49라면 i가 7인 경우도 포함해서 봐야함
        for(int i=2; i<=(int)Math.sqrt(num); i++) {
            if(num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}