[코테연습] k진수에서 소수 개수 구하기

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

🔹 k진수에서 소수 개수 구하기 문제 분석 및 풀이

📌 문제 개요
• 자연수 n을 k진수로 변환한 후, 숫자들을 0을 기준으로 나눈다.
• 나눠진 숫자들 중에서 소수의 개수를 구하는 문제.

📌 문제 타입
• 문자열 처리
• 진법 변환
• 소수 판별
• 수학적 계산

📌 문제 분석
1. n을 k진법으로 변환해야 한다.
2. 변환된 k진수에서 0을 기준으로 숫자들을 분리한다.
3. 분리된 숫자들이 소수인지 판별해야 한다.
4. 소수 개수를 카운트하여 반환한다.

📌 문제 풀이 (Bullet Point)

1. n을 k진수로 변환
• Long.toString(n, k)를 사용하여 k진법으로 변환.
• 예시: n = 437674, k = 3 → 211020101011

2. 0을 기준으로 숫자를 분리
• split("0")을 사용하여 0을 기준으로 나눔.
• 예시: "211020101011" → ["211", "2", "1", "101", "11"]
• 빈 문자열("")이 나올 수도 있으므로 처리 필요.

3. 각 숫자를 소수 판별
• 1은 소수가 아님 → 예외 처리.
• 소수 판별은 Math.sqrt(num)까지 반복문을 돌며 확인.

4. 소수 개수 카운트 후 반환
• 소수인 경우 개수를 증가시키고 최종적으로 반환.

📌 시간 복잡도 분석
• 진법 변환: O(log n)
• 문자열 분리: O(n)
• 소수 판별: 평균적으로 O(√m) (m은 변환된 숫자의 크기)
• 전체 복잡도: O(n log n) 정도로 볼 수 있음. (최악의 경우)

📌 예제

입력

n = 437674, k = 3

변환된 k진수

"211020101011"

분리된 숫자

["211", "2", "1", "101", "11"]

소수 판별

211 (소수) ✅
2 (소수) ✅
1 (소수 아님) ❌
101 (소수) ✅
11 (소수) ✅

출력

4

✔ 최종적으로 소수 개수는 4!


Java

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        // 주어진 숫자 n을 k진법으로 변환하여 문자열로 저장
        String x = Long.toString(n, k);
        
        // 변환된 숫자를 '0'을 기준으로 분할하여 배열로 저장
        String[] arr = x.split("0");
        
        // 배열을 순회하면서 소수인 경우 answer 증가
        for (String str : arr) {
            if (str.isEmpty()) continue; // 빈 문자열이면 건너뜀
            
            // 문자열을 숫자로 변환한 후 소수 판별
            if (isPrime(Long.parseLong(str))) {
                answer += 1; // 소수일 경우 개수 증가
            }
        }
        
        return answer; // 최종 소수 개수 반환
    }
    
    // 소수 판별 함수
    static boolean isPrime(long num) {
        if (num == 1) return false; // 1은 소수가 아님
        
        // 2부터 √num까지 나눠서 나누어 떨어지면 소수가 아님
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false; // 나누어 떨어지면 소수가 아님
            }
        }
        return true; // 나누어 떨어지는 수가 없으면 소수
    }
}