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

📝 문제 설명

양의 정수 n을 k진수로 변환했을 때, 변환된 수 안에 있는 조건에 맞는 소수(Prime Number)의 개수를 구하는 문제입니다.

• 소수는 숫자 사이사이에 있는 '0'을 기준으로 분리된 수여야 합니다.
• 각 분리된 수가 소수인지 판별할 때, 매우 큰 수가 나올 수 있음을 유의해야 합니다.

---

💡 접근 방식

1. k진수 변환

자바의 Integer.toString(n, k) 메서드를 활용하여 10진수 n을 간단하게 k진수 문자열로 변환했습니다.

2. 0을 기준으로 숫자 분리 (투 포인터 활용)

단순히 split("0")을 사용할 수도 있지만, 이번 풀이에서는 lt와 rt라는 두 인덱스를 활용하여 문자열을 직접 파싱했습니다.

• rt를 한 칸씩 이동시키며 '0'을 만날 때마다 lt부터 rt까지의 부분 문자열을 추출합니다.
• 마지막 숫자가 '0'으로 끝나지 않는 경우를 대비해 rt == num.length() 조건에서 마지막 구간을 처리했습니다.
• 00처럼 0이 연속되는 경우 빈 문자열이 생성될 수 있으므로 isEmpty() 체크를 통해 예외 처리를 진행했습니다.

3. 소수 판별 알고리즘 (핵심)

이 문제의 핵심은 효율적인 소수 판별과 데이터 타입입니다.

• 시간 복잡도 최적화: $O(\sqrt{N})$ 방식인 제곱근까지의 나누기 방식을 채택했습니다. i <= Math.sqrt(sub)와 같이 등호를 포함하여 제곱근 값 자체도 검사해야 정확한 판별이 가능합니다.
• 데이터 타입: k진수로 변환된 숫자가 매우 길어질 수 있으므로, int 범위를 넘어설 것에 대비해 Long.parseLong()과 long 타입을 사용했습니다.

---

💻 구현 코드 (Java)

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        String num = Integer.toString(n, k);
        
        int lt = -1;
        int rt = 0;
        
        while(rt <= num.length()){
            if(rt == num.length()){
                String temp = num.substring(lt+1, rt);
                if(temp.isEmpty() || temp == null) continue;
                long sub = Long.parseLong(temp);
                if(prime(sub)) answer++;
                break;
            }
            
            if(num.charAt(rt) == '0') {
                String temp = num.substring(lt+1, rt);
                if(temp.isEmpty()){
                    rt++;
                    continue;
                } 
                long sub = Long.parseLong(temp);
                if(prime(sub)) answer++;
                lt = rt;
            }
            rt++;
        }
        
        return answer;
    }
    
    public boolean prime(long sub) {
        if(sub < 2) return false;
        for(int i=2; i <= Math.sqrt(sub); i++) {
            if(sub % i == 0) return false;
        }
        return true;
    }
}

✨ 느낀 점

✅ 시간 초과와 등호 하나(<=)의 차이

처음 구현 시 소수 판별 반복문에서 i < Math.sqrt(sub)라고 작성하여 일부 테스트 케이스에서 실패하거나 시간 초과가 발생할 뻔했습니다. 제곱근 값까지 정확히 확인해야 한다는 점(<=)이 소수 판별 알고리즘의 핵심임을 다시금 깨달았습니다.

✅ Long 타입의 중요성

알고리즘 문제에서 "숫자가 크다"는 힌트가 보이면 습관적으로 long 타입을 고려해야 한다는 것을 배웠습니다. 특히 진수 변환 문제는 자릿수가 급격히 늘어날 수 있다는 점을 항상 유의해야겠습니다.

✅ 유연한 문자열 처리

split()을 사용하면 코드가 더 간결해질 수 있다는 점을 배웠습니다. 이번에는 인덱스를 직접 다루는 방식으로 풀이하며 문자열 슬라이싱에 대한 이해도를 높였지만, 실전에서는 상황에 맞는 더 효율적인 라이브러리 활용 능력을 키워야겠다고 생각했습니다.

---