[lv2] k진수에서 소수 개수 구하기

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

 

헤맨 이유

 

본문 :

 

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.)

=> 숫자를 10진수로 변환하라는 뜻으로 착각 (10진법으로 표시된 수로 여기라는 뜻이었다.)

 

놓친 것

소수에는 1이 포함되지 않음

 

class Solution {
    public int solution(int n, int k) {

        return getCnt(Integer.toString(n, k), k);
    }

    static int getCnt(String num, int k) {
        int cnt = 0;
        int N = num.length();

        for(int i=0; i<N; i++) {
            for(int j=i+1; j<=N; j++) {
                String now = num.substring(i, j);
                int size = j - i;
                int r = i + size;
                int l = i - 1;

                long n = Long.valueOf(now);

                // 각 자릿수에 0을 포함하지 않는 소수
                if(hasZero(now) || !isPrime(n))
                    continue;

                // 소수 양쪽에 0이 있는 경우
                if(l >= 0 && r < N && num.charAt(l) == '0' && num.charAt(r) == '0')
                    cnt++;
                    // 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
                else if(r < N && l == -1 && num.charAt(r) == '0')
                    cnt++;
                    // 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
                else if(l >= 0 && r == N && num.charAt(l) == '0')
                    cnt++;
                    // 소수 양쪽에 아무것도 없는 경우
                else if(l == -1 && r == N)
                    cnt++;
            }
        }

        return cnt;
    }

    // 10진법 기준 소수 판별
    static boolean isPrime(long n) {

        if(n == 1)
            return false;

        long sqrt = (long) Math.sqrt(n);

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

        return true;
    }

    // k진법 기준 0포함 체크
    static boolean hasZero(String num) {

        for(int i=0; i<num.length(); i++) {
            if(num.charAt(i) == '0')
                return true;
        }

        return false;
    }

}