k진수에서 소수 개수 구하기_복습2

2026.09.30

문제 풀이

1차 실행 오류

---

86.9/100.0

런타임 에러

---

런타임 에러 원인 분석

int 가 표현할 수 있는 값의 범위를 넘어가는 경우가 발생한다.

---

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

나의 코드

---

소요 시간: 32분
시간 복잡도: $O(√V)$

---

class Solution {
    private boolean isPrime(long n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;    
            }
        }
        return true;
    }
    public int solution(int n, int k) {  
        int cnt = 0;
        String s = Integer.toString(n, k);
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.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++;
        }
        sb.setLength(0);
        return cnt;
    }
}

AI 코드

---

시간 복잡도: $O(√V)$

---

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

    private boolean isPrime(long v) {
        if (v < 2) return false;
        if (v < 4) return true;            // 2, 3
        if (v % 2 == 0 || v % 3 == 0) return false;
        // 6k±1 형태만 검사 (2, 3의 배수는 이미 걸러짐)
        for (long i = 5; i * i <= v; i += 6) {
            if (v % i == 0 || v % (i + 2) == 0) return false;
        }
        return true;
    }
}

문제 풀이 후기

실행을 하면서 런타임 오류를 잡는 데에 실패했다.
int 의 표현 범위 오류도 고려했으나, n <= 1,000,000 의 범위를 가지기에
범위 초과 오류가 일어날 것이라고 생각하지 못했다.

코드를 주석 처리해가며 런타임 오류가 발생한 부분은 찾아냈으나,
왜 발생하는지를 알아차리지 못했다.