[프로그래머스] Lv.2 : k진수에서 소수 개수 구하기 - 자바[Java]

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

프로그래머스

풀이

1. n을 k진수 문자열로 변환

2. "0"을 기준으로 문자열 나누기

3. 각 문자열을 숫자로 변환 후, 그 숫자가 소수인지 판별하여 소수 개수를 카운트한다.

 

주의할 점

- n은 100만 이하이며 2진수 등으로 변환했을때 int 범위를 벗어날 수 있다. 따라서 Long.parseLong()을 사용해야한다.

- 소수 판별 로직에서 for문 탈출 조건을 i * i <= num으로 할 경우, i * i가 int 범위를 넘어설수있으므로, i < Math.sqrt(num) + 1 을 사용한다. 또는 (double)i * i <= num 으로 해야 한다.

코드

class Solution {
    
    public int solution(int n, int k) {
        // n을 k진수 수로 바꾸기
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            int mod = n % k;
            n /= k;
            sb.append(mod);
        }
        
        // 0을 기준으로 문자열 나누기
        String[] numbers = sb.reverse().toString().split("0");
        
        // 각 문자열을 숫자로 변환할 때 해당 수가 소수인지 판별
        int cnt = 0;
        for (String number: numbers) {
            if (number.equals("")) continue;
            
            Long num = Long.parseLong(number); // Long
            if (isPrime(num)) {
                    cnt++;
            }
        }
        
        return cnt;
    }
    
    static boolean isPrime(Long num) {
        if (num == 2) return true;
        if (num == 1 || num % 2 == 0) return false;

        // i * i <= num 을 사용하면, i * i가 int의 범위를 넘어설 수 있다.
        for(int i = 3; i < Math.sqrt(num) + 1; i += 2) {
            if(num % i == 0) return false;
        }
        
        return true;
    }
}