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

프로그래머스

 

풀이

 

1. 숫자 n을 k진수로 바꾸는 방법

String binary_k = Long.toString(n, k);

 

2. 공백 여러 개를 한번에 제거하는 방법

String binary = binary_k.replaceAll("\\s+", "");

 

3. 반례(테스트 1번, 11번)

long 길이만큼의 숫자가 들어가게 된다면, 에라스토테네스 체로 소수 판별이 불가능하다는 생각이 들었다.

그래서 binary배열 안의 long num을 isPrime이라는 메서드로 넘겨 소수인지 판별해줬다.

    static boolean isPrime(long n){
        if(n == 1){
            return true;
        }
        long sqrt = (long) Math.sqrt(n) + 1;
        for(int i=2; i<sqrt; i++){
            if(n%i == 0){
                return true;
            }
        }
        return false;
    }

 

n == 1일때는 따로 처리해줘야 한다.

 

전체코드

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        String binary_k = Long.toString(n, k);
        binary_k = binary_k.replaceAll("0", " ");
        
        String binary[] = binary_k.split("\\s+");
        for(int i=0; i<binary.length; i++){
            long num = Long.valueOf(binary[i]);
            boolean flag = isPrime(num);
            if(!flag){
                answer++;
            }
        }
        
        return answer;
    }
    static boolean isPrime(long n){
        if(n == 1){
            return true;
        }
        long sqrt = (long) Math.sqrt(n) + 1;
        for(int i=2; i<sqrt; i++){
            if(n%i == 0){
                return true;
            }
        }
        return false;
    }
}