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

 

🧫 문제 분석

✔️ 출처

K진수에서 소수 개수 구하기 level 2

📖 문제

 

간단한 문제인데 소수 판별 문제를 오랜만에 만나서 

리마인드 겸 포스팅한다.

 

조건이 뭔가 4가지 경우를 다 체크해야할 것 같지만 그렇지 않다

11101110111

0을 기준으로 진수를 나누면

1가지의 조건식만 적용된다

첫번째와 마지막은 각각 P0, 0P

가운데는 무조건 0P0이 적용된다.

이들을 하나하나 다 소수검증해준다. 

 

문제에서 k진법으로가 아닌 10진법으로봤을때 소수여야한다고 되어있는데 이는

211 일 경우 10진수 그대로 211이 소수이냐는 것이다..

 

4번 조건 P의 경우 0을 기준으로 진수를 나눴을떄

각 자릿수에 0이 하나도 없어야하므로 그대로 나온다.

따라서 똑같이 적용하면된다. 

 

---

🔅 문제 풀이

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int tmp = n;
        
        // k진수로 변환
        while(tmp!= 0) {
            int rs = tmp % k;
            stack.push(rs);
            tmp /= k;
        }
        
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        
        String[] split = sb.toString().split("0+");
       
        // 0을 제외한 각 구간별 소수 판별
        for (int i = 0; i < split.length; i++) {
            long num = Long.parseLong(split[i]);
            if (isPrime(num)) {
                answer++;
            }
        }
        
        return answer;
    }
    
    private boolean isPrime(long n) {
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

 

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식

1.