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

문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

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

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

---

제한사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

---

입출력 예

n k result

437674	3	3
110011	10	2

---

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.

package LV2;

public class H92335 {
    public int solution(int n, int k) {
        // 변환된 k진수를 저장할 String 변수
        String num = Integer.toString(n, k);

        // k진수를 '0'을 기준으로 split
        String[] numArr = num.split("0");

        int count = 0; // 소수 개수를 저장할 변수

        for (String str : numArr) {
            // 공백은 continue
            if (str.equals("")) continue;

            // 10진법으로 변환
            int decimalNum = Integer.parseInt(str);

            // 소수 판별
            if (isPrime(decimalNum)) {
                count++;
            }
        }

        return count;
    }

    // 소수 판별 메서드
    public boolean isPrime(int n) {
        if (n < 2) return false; // 2보다 작으면 소수 아님
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false; // 나눠떨어지면 소수 아님
        }
        return true; // 그 외의 경우는 소수
    }
}

런타임 에러….ㅠㅠㅠㅠ

실행 중에 예상치 못한 문제를 발견했을 때 발생한다. 일반적으로 런타임 에러의 원인은 잘못된 타입의 값이 함수에 전달되거나, 배열의 범위를 벗어나는 접근 등이 있다.

이 경우, **Integer.parseInt(str)**에서 발생할 수 있는 NumberFormatException 예외를 처리하지 않아서 그럴 수 있다. k진수로 변환한 수 중에서 10진법으로 표현할 수 없는 숫자가 있을 경우, **Integer.parseInt(str)**에서 NumberFormatException 예외가 발생할 수 있다.

package LV2;

public class H92335 {
    // 소수 판별 함수
    public boolean isPrime(long n) {
        if(n == 1)  return false;  // 1은 소수가 아니므로 false 반환
        long a = (long)Math.sqrt(n) + 1;  // n의 제곱근 계산
        for(int i=2;i<a;i++) {  // 2부터 n의 제곱근까지 반복
            if(n%i == 0) return false;  // 나누어 떨어지는 수가 있으면 소수가 아니므로 false 반환
        }
        return true;  // 나누어 떨어지는 수가 없으면 소수이므로 true 반환
    }

    // 주어진 숫자를 k진수로 바꾸고, 0을 기준으로 나누는 함수
    public String[] makeBinList(int n, int k) {
        StringBuilder kBin = new StringBuilder();  // k진수를 저장할 StringBuilder
        while(n != 0) {
            kBin.insert(0, n%k);  // n을 k로 나눈 나머지를 문자열 앞에 추가
            n /= k;  // n을 k로 나눔
        }    // k진수 생성
        String[] binList = kBin.toString().split("0");  // 생성된 k진수를 '0'을 기준으로 나눔
        // 0을 기준으로 나눈 문자열 배열 반환
        return binList;
    }

    // 솔루션 함수
    public int solution(int n, int k) {
        int answer = 0;  // 소수의 개수를 저장할 변수

        String[] a = makeBinList(n, k);  // k진수로 변환된 문자열 배열을 가져옴

        for(String b : a) {  // 문자열 배열을 반복
            if(b.equals(""))  continue;  // 문자열이 비어있으면 다음 반복으로 건너뜀

            long c = Long.parseLong(b);  // 문자열을 long으로 변환
            if(isPrime(c))    answer++;  // 변환된 숫자가 소수이면 answer 증가
        }

        // 소수의 개수 반환
        return answer;
    }
}

주어진 정수를 k진수로 변환하고, 이진수를 '0'을 기준으로 나눠 각 부분이 소수인지 확인하는 알고리즘을 구현한 것이다. 'isPrime' 함수는 주어진 수가 소수인지 판별하고, 'makeBinList' 함수는 주어진 수를 k진수로 변환한 후 '0'을 기준으로 나눠 문자열 배열로 반환한다.