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

하이솝·2026년 4월 29일

2026.04.29

문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

0P0처럼 소수 양쪽에 0이 있는 경우
P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
P처럼 소수 양쪽에 아무것도 없는 경우
단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
- 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

제한 사항

1 ≤ n ≤ 1,000,000
3 ≤ k ≤ 10

입출력 예

문제 풀이

1차 실행 오류

런타임 에러 및 실패
str에 0이 저장되는 경우 발생

import java.util.List;
import java.util.ArrayList;

class Solution {
    private String str = "";
    private List<Integer> list = new ArrayList<>();
    public void baseK(int num, int k) {
        if (num == 0) {
            return;
        }
        baseK(num / k, k);
        if (str != "" && (num % k) == 0) {
            list.add(Integer.parseInt(str));
            str = "";
        }
        else {
            str += String.valueOf(num % k);
        }
    }
    public boolean isPrime(int num) {
        if (num == 1) {
            return false;
        }
        for (int i = 2; i < num / 2; i++) {
            if (num % 2 == 0) {
                return false;
            }
        }
        return true;
    }
    public int solution(int n, int k) {
        int answer = 0;
        baseK(n, k);
        if (str != "") { // n이 비지 않았을 때
            list.add(Integer.parseInt(str));
        }
        for (int i = 0; i < list.size(); i++) {
            if (isPrime(list.get(i))) {
                answer++;
            }
        }
        return answer;
    }
}

2차 실행 오류

런타임 오류 및 실패
String을 ==를 이용한 비교 오류, .equals()사용해야함
isPrime() i % 2로만 나누는 오류 발견

import java.util.List;
import java.util.ArrayList;

class Solution {
    private String str = "";
    private List<Integer> list = new ArrayList<>();
    public void baseK(int num, int k) {
        if (num == 0) {
            return;
        }
        baseK(num / k, k);
        if (str != "" && (num % k) == 0) {
            list.add(Integer.parseInt(str));
            str = "";
        }
        else if (num % k != 0) {
            str += String.valueOf(num % k);
        }
    }
    public boolean isPrime(int num) {
        if (num == 1) {
            return false;
        }
        for (int i = 2; i < num / 2; i++) {
            if (num % 2 == 0) {
                return false;
            }
        }
        return true;
    }
    public int solution(int n, int k) {
        int answer = 0;
        baseK(n, k);
        if (str != "") { // n이 비지 않았을 때
            list.add(Integer.parseInt(str));
        }
        for (int i = 0; i < list.size(); i++) {
            if (isPrime(list.get(i))) {
                answer++;
            }
        }
        return answer;
    }
}

3차 실행 오류

런타임 오류

import java.util.List;
import java.util.ArrayList;

class Solution {
    private String str = "";
    private List<Integer> list = new ArrayList<>();
    public void baseK(int num, int k) {
        if (num == 0) {
            return;
        }
        baseK(num / k, k);
        if (!str.equals("") && (num % k) == 0) { // str이 비어있지 않고, num % k == 0일 때 저장
            list.add(Integer.parseInt(str));
            str = "";
        }
        else if (num % k != 0) { // str에는 0 저장하지 않음
            str += String.valueOf(num % k);
        }
    }
    public boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
        for (int i = 2; i < num / 2; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    public int solution(int n, int k) {
        int answer = 0;
        baseK(n, k);
        if (!str.equals("")) { // n이 비지 않았을 때
            list.add(Integer.parseInt(str));
        }
        for (int i = 0; i < list.size(); i++) {
            if (isPrime(list.get(i))) {
                answer++;
            }
        }
        return answer;
    }
}

나의 코드(AI 활용)

소요 시간: 58분

시간 복잡도: O(√n × log n)

int로 변환되는 수가 범위를 초과할 가능성이 있기 때문에
long 타입으로 선언해주어야 함
타입의 범위 초과 오류를 고려해서 코드를 작성할 것

import java.util.List;
import java.util.ArrayList;

class Solution {
    private String str = "";
    private List<Long> list = new ArrayList<>();
    public void baseK(int num, int k) {
        if (num == 0) {
            return;
        }
        baseK(num / k, k);
        if ((num % k) == 0) { // str이 비어있지 않고, num % k == 0일 때 저장
            if (!str.equals("")) {
                list.add(Long.parseLong(str));
                str = "";
            }
        }
        else { // str에는 0 저장하지 않음
            str += String.valueOf(num % k);
        }
    }
    public boolean isPrime(long num) {
        if (num < 2) {
            return false;
        }
        for (long i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    public int solution(int n, int k) {
        int answer = 0;
        baseK(n, k);
        if (!str.equals("")) { // n이 비지 않았을 때
            list.add(Long.parseLong(str));
        }
        for (int i = 0; i < list.size(); i++) {
            if (isPrime(list.get(i))) {
                answer++;
            }
        }
        return answer;
    }
}

AI 코드

.toString() 오버로딩 방법에 따라

1) 그냥 문자열 반환
2) n진수를 문자열로 반환

class Solution {
    public boolean isPrime(long num) {
        if (num < 2) return false;
        for (long i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    public int solution(int n, int k) {
        // 1. k진수 변환 (Java 내장 함수 사용)
        String converted = Integer.toString(n, k);
        
        // 2. 0으로 split 후 바로 소수 판별
        int answer = 0;
        for (String part : converted.split("0", -1)) {
            if (part.isEmpty()) continue;
            if (isPrime(Long.parseLong(part))) answer++;
        }
        
        return answer;
    }
}