[프로그래머스/Java] k진수에서 소수 개수 구하기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/92335?language=java

프로그래머스

양의 정수 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개입니다.
  이와 같이 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.

 

내가 작성한 코드

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        // 소수 개수 저장할 변수 생성
        int answer = 0;
        
        // n을 k진수 문자열로 변환
        String baseK = Integer.toString(n, k);
        
        // '0'을 기준으로 구간 분리 (연속된 0도 한 번에 끊기도록 "0+")
        String[] parts = baseK.split("0+");
        
        // 각 구간이 소수인지 판별
        for (String p : parts) {
            // 빈 문자열 방어 
            if (p.isEmpty()) continue;
            
            // k <= 10이므로 p는 0~9 숫자만. 그대로 10진수로 파싱
            long num = Long.parseLong(p);
            
            if (isPrime(num)) {
                answer++;
            }
        }
        
        return answer;
    }
    
    // 소수 판별: √n까지만 확인
    private boolean isPrime(long x) {
        // 0, 1 제외
        if (x < 2) return false;
        // 2는 소수
        if (x == 2) return true;
        // 짝수 제거
        if (x % 2 == 0) return false;
        
        // √x 까지만 나누기
        long limit = (long) Math.sqrt(x);
        
        // 이미 짝수는 위에서 걸렀으므로 홀수만 확인
        for (long l = 3; l <= limit; l += 2) {
            if (x % l == 0) return false;
        }
        
        return true;
    }
}

문제를 풀기 위해 생각한 방향

처음 문제를 봤을 때, 핵심은 주어진 정수 n을 k진수로 변환한 뒤 0을 기준으로 잘라 생긴 수들 중 소수의 개수를 세는 것이라는 점을 파악했다. 단순히 진법 변환과 소수 판별 두 가지 과정을 조합하면 해결할 수 있는 문제라고 판단했다.

조건을 분석해 보면 먼저 n을 k진수로 바꾸는 과정이 필요하다. 자바에서는 Integer.toString(n, k)를 사용하면 손쉽게 문자열 형태의 k진수를 얻을 수 있다. 그다음에는 0을 기준으로 문자열을 분리해야 하는데, 이때 단순히 split("0") 대신 split("0+")를 사용하면 연속된 0을 한 번에 잘라낼 수 있어 불필요한 빈 문자열을 줄일 수 있다. 그래도 split 결과에는 빈 문자열이나 1 같은 소수가 아닌 값이 포함될 수 있으므로 이를 미리 걸러주는 처리가 필요하다.

소수 판별은 가장 중요한 부분이다. 일반적으로 어떤 수가 소수인지 확인하려면 2부터 자기 자신 전까지 모든 수로 나눠봐야 하지만, 이는 비효율적이다. 따라서 √n까지만 검사해도 충분하다는 성질을 이용하는 것이 좋다. 먼저 0과 1은 소수가 아니므로 제외하고, 2는 유일한 짝수 소수이므로 바로 소수로 처리한다. 그 외 짝수는 전부 합성수이므로 빠르게 거르고, 홀수만 √n까지 검사하면 된다. 이렇게 하면 큰 수에 대해서도 시간 내에 판별이 가능하다.

이 과정을 정리하면, n을 k진수로 변환 → 0으로 분리 → 숫자 하나하나를 10진수로 변환 → 소수 판별 → 카운트라는 흐름으로 풀이를 완성할 수 있다. 시간 복잡도는 각 조각의 길이에 따라 달라지지만, 소수 판별을 √n까지만 하므로 충분히 효율적이다.