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

2026.08.12

문제 풀이

1차 실행 오류

---

86.9/100

런타임 에러

---

런타임 에러 원인 분석

n = 797161, k = 3 (n을 k진수로 변환하면 1111111111111에 해당함)
int로 전부 담을 수 없음

---

class Solution {
    public int solution(int n, int k) {
        int cnt = 0;
        String baseK = Integer.toString(n, k);
                
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < baseK.length(); i++) {
            char c = baseK.charAt(i);
            if (c == '0') {
                if (!sb.isEmpty() && isPrime(Integer.parseInt(sb.toString()))) {
                    cnt++;
                }
                sb.setLength(0);
            }
            else {
                sb.append(c);
            }
        }
        if (!sb.isEmpty() && isPrime(Integer.parseInt(sb.toString()))) {
            cnt++;
        }
        return cnt;
    }
    private boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        int limit = (int)Math.sqrt(n);
        for (int i = 2; i <= limit; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

나의 코드

---

소요 시간: 42분
시간 복잡도: $O(√(10^{log_k n}))$

---

class Solution {
    private boolean isPrime(long n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        int limit = (int)Math.sqrt(n);
        for (int i = 2; i <= limit; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    public int solution(int n, int k) {        
        int cnt = 0;
        String baseK = Integer.toString(n, k);           
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < baseK.length(); i++) {
            char c = baseK.charAt(i);
            if (c == '0') {
                if (!sb.isEmpty() && isPrime(Long.parseLong(sb.toString()))) {
                    cnt++;
                }
                sb.setLength(0);
            }
            else {
                sb.append(c);
            }
        }
        if (!sb.isEmpty() && isPrime(Long.parseLong(sb.toString()))) {
            cnt++;
        }
        return cnt;
    }
}

AI 코드

---

시간 복잡도: $O(√(10^{log_k n}))$

---

코드 분석

전체적인 구조는 동일하나 split("0")을 사용해서
길었던 if/else문을 단번에 정리했음

sb.isEmpty()는 Java 15에서 추가된 메서드이기 때문에
이전 버전에서는 오류가 발생할 수 있음.

---

class Solution {
    public int solution(int n, int k) {
        int cnt = 0;
        for (String s : Integer.toString(n, k).split("0")) {
            if (!s.isEmpty() && isPrime(Long.parseLong(s))) cnt++;
        }
        return cnt;
    }

    private boolean isPrime(long num) {
        if (num <= 1) return false;
        if (num <= 3) return true;          // 2, 3
        if (num % 2 == 0) return false;     // 짝수 선제거

        for (long i = 3; i * i <= num; i += 2) {   // 홀수만 검사
            if (num % i == 0) return false;
        }
        return true;
    }
}

문제 풀이 후기

split()과 같은 문자열 메서드를 활용할 생각을 하지 못해봤다.
내가 이미 알고 있는 지식들만 하더라도 다방면으로 응용이 가능하며,
엄청난 활용이 가능하다는 것을 깨달을 수 있었다.