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

문제 링크

---

1. 문제 분석

주어진 n을 k진법으로 변환한 후, 연속된 0으로 둘러싸여 있거나 독립적으로 존재하는 소수의 개수를 찾는 문제입니다.
즉, k진법 변환과 소수 판별을 수행해야 합니다.

주요 고려 사항

1. n을 k진법으로 변환
   • n을 k로 나눈 나머지를 저장하면서 변환 수행
2. 변환된 문자열에서 0을 기준으로 나누어 소수 후보 추출
   • 연속된 0 사이에 있는 숫자들을 저장
3. 각 숫자가 소수인지 판별
   • 1이 포함된 경우는 소수에서 제외해야 함
   • 소수 판별을 효율적으로 수행해야 함 (에라토스테네스의 체 또는 제곱근까지만 확인)

---

2. 해결 방법

1. k진법 변환
   • n을 k로 나눈 나머지를 Deque에 저장
   • 마지막에 pollLast()로 하나씩 꺼내면서 변환된 숫자를 만듦
2. 0을 기준으로 숫자 분리
   • 0P0, P0, 0P, P 형태의 숫자 추출
   • 0을 만나면 현재 숫자를 List<Long>에 저장 후 초기화
3. 소수 판별
   • 1인 경우 제외
   • isDecimal() 함수를 사용하여 소수 판별
   • sqrt(n)까지만 나누어보며 소수 여부 판단

---

3. 코드 구현

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;

        Deque<Integer> s = new ArrayDeque<>();
        s.add(0);

        while (n > 0) {
            s.add(n % k);
            n /= k;
        }

        List<Long> candidate = new ArrayList<>();

        long sum = 0;        
        while (!s.isEmpty()) {

            if(s.getLast() == 0) {
                if(sum != 0)
                   candidate.add(sum);
                sum = 0;
            }

            sum *= 10;
            sum += s.pollLast();
        }

        for (int i = 0; i < candidate.size(); i++) {

            if(candidate.get(i) == 1) continue;

            if(isDecimal(candidate.get(i)))
                answer++;
        }

        return answer;
    }

    public boolean isDecimal(long n) {

        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0) return false;

        // 3부터 √n까지 홀수만 체크
        for (long i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

---

4. 코드 분석

1. k진법 변환

while (n > 0) {
    s.add(n % k);
    n /= k;
}

• Deque<Integer>에 n을 k로 나눈 나머지를 저장하며 k진법 변환 수행
• 마지막에 pollLast()를 이용해 변환된 값을 정순으로 만듦

2. 0을 기준으로 숫자 분리

while (!s.isEmpty()) {
    if(s.getLast() == 0) {
        if(sum != 0)
            candidate.add(sum);
        sum = 0;
    }
    sum *= 10;
    sum += s.pollLast();
}

• 0을 만나면 현재까지 모인 숫자를 candidate 리스트에 추가
• 0이 아닌 경우 계속 숫자를 이어붙임

3. 소수 판별

if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0) return false;

for (long i = 3; i * i <= n; i += 2) {
    if (n % i == 0) return false;
}
return true;

• 1은 소수가 아님을 고려
• 짝수는 2만 소수로 인정
• 3부터 √n까지 홀수만 검사하여 소수 여부 확인 (시간 복잡도 O(√N))

---

5. 개선할 점 및 대체 방법

1. String 활용한 k진법 변환
   • Deque를 사용할 필요 없이 Integer.toString(n, k)를 이용하여 변환 가능

     String kBase = Integer.toString(n, k);
     String[] parts = kBase.split("0"); // 0을 기준으로 분리

   • 장점: 코드 간결화, String API 활용 가능
   • 단점: 메모리 사용량 증가 가능
2. 소수 판별 최적화
   • 에라토스테네스의 체를 미리 적용하여 소수 여부를 빠르게 판별 가능
   • 하지만, 이 문제에서는 최대 1,000,000 이하의 소수 판별만 수행하므로 O(√N) 방식이 더 적절함