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

2026.10.05

문제 풀이

나의 코드

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

class Solution {
    public boolean isPrime(long 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); // 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)$
코드 분석
split("0") 으로 미리 숫자 부분을 분리했다.

소수 판별에서는 2와 3으로 나눠지는 수를 미리 판별하고,
6k + 1 로 나눠지는 수에 대해서만 검사를 진행했다.

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;
        if (v % 2 == 0 || v % 3 == 0) return false;
        for (long i = 5; i * i <= v; i += 6) {
            if (v % i == 0 || v % (i + 2) == 0) return false;
        }
        return true;
    }
}

문제 풀이 후기

이제부터 1주일이라는 일정 기간을 두고
이전 주에 틀렸던 문제들을 복습하는 시간을 가지기로 했다.
적당히 기억나면서도 적당히 기억나지 않는 이 타이밍에
내가 이 문제에 대해 잘 기억하고 있나 확인하기 위해서이다.