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

문제

양의 정수 n을 k진수로 바꿨을 때, 변환된 수 안에 조건에 맞는 소수(Prime number)가 몇 개인지 찾는 문제입니다. 소수 양쪽, 오른쪽, 왼쪽 중 한 곳 이상에 '0'이 존재해야 하며, 소수 각 자릿수에는 '0'이 포함되지 않아야 합니다. (예: 101은 조건에 맞는 소수가 될 수 없음) 또한 추출된 숫자는 k진법 기준이 아닌, 10진법 기준으로 소수인지 판별해야 합니다.

• 입력: 양의 정수 n (1 ≤ n ≤ 1,000,000)과 진법 k (3 ≤ k ≤ 10)
• 출력: 조건에 맞는 소수의 개수를 반환합니다.

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

풀이: 문자열 분리를 활용한 조건 필터링

소수의 양쪽 또는 한쪽에 '0'이 있어야 하고 소수 내부에는 '0'이 없어야 한다는 복잡한 조건은, 결국 "문자열을 '0'을 기준으로 잘라낸 조각들"을 의미합니다. 자바의 Integer.toString과 split 메서드를 활용하면 이 조건들을 한 번에 해결할 수 있습니다.

• 진법 변환 및 분리: Integer.toString(n, k)를 통해 n을 k진수 문자열로 변환합니다. 변환된 문자열을 split("0")을 통해 0을 기준으로 잘라내어 숫자로 이루어진 문자열 조각 배열을 만듭니다. 연속된 0으로 인해 생긴 빈 문자열 조각은 무시합니다.
• 소수 판별 로직 최적화: 숫자 x의 제곱근까지만 반복문을 돌며 나누어 떨어지는지 검사합니다.
• 자료형 오버플로우 주의: n은 1,000,000 이하의 수이지만, 이를 3진수 등으로 변환하면 문자열의 길이가 상당히 길어질 수 있습니다. 이 조각을 10진수로 파싱하여 소수 판별을 할 때, 자바의 int형 최대치(약 21억)를 초과하여 NumberFormatException이 발생할 수 있습니다. 따라서 반드시 Long.parseLong을 사용하고 소수 판별 로직의 변수도 long으로 처리해야 합니다.

코드

class Solution {
    public int solution(int n, int k) {
        // n을 k진수 문자열로 변환
        String s = Integer.toString(n, k);
        // '0'을 기준으로 문자열 분리 (조건에 맞는 숫자 덩어리 추출)
        String[] a = s.split("0");
        
        int ans = 0;
        for (String t : a) {
            // 빈 문자열이 아니고, 10진수 기준으로 소수라면 카운트 증가
            if (t.length() != 0 && isPrime(t)) {
                ans++;
            }
        }
        
        return ans;
    }
    
    public boolean isPrime(String s) {
        // int 범위를 초과할 수 있으므로 반드시 long 타입으로 파싱
        long x = Long.parseLong(s);
        
        if (x <= 1) return false;
        
        // O(sqrt(N)) 최적화로 소수 판별
        for (long i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

알고리즘 분류

수학 (Mathematics), 문자열 (String), 소수 판별 (Primality Test)