Java 백준 문제풀이 (52) 2023_신기한 소수

 

문제 이름을 신기한 소수가 아닌 신기한 수빈이로 바꾸면 좋겠다.

바로 본론으로 들어가서 문제 조건을 정리해보자.

내가 처음 작성한 주석은 다음과 같다.

 

        // 신기한 소수 구하기 (모든 자리 수가 소수다)
        // N의 최대값이 8 -> 즉 입력값의 최대 값이 9999만
        // 에라토스테네스의 체로 소수를 구할 경우 400mb(400000000byte)를 차지하는데 문제에서 제시하는 메모리 제한은 4MB
        // 따라서 매번 소수를 새롭게 구해야 한다.
        // 모든 경우의 수를 구하는 문제이므로 dfs

 

난 소수 문제를  풀 때 에라토스테네스의 체를 사용하는 것을 좋아하는데

예전에 메모리 문제로 삽질해본 이후 항상 이런 문제를 보면 문제에서 제시하는 메모리 부터 확인한다.

 

다만 지금 글을 작성하면서 생각해보니 주석의 내용은 잘못됐다.

일반적으로 에라토스테네스의 체 알고리즘 사용 시 boolean 배열을 사용하니 boolean 자료형의 크기는 1byte이므로 400mb가 아니라 100mb의 용량이 필요하다.

 

이렇든 저렇든 4mb 메모리로 부족한 것은 마찬가지다.

따라서 매번 새롭게 소수를 구할 필요가 있다.

 

알겠지만 매번 소수를 구하는 게 어렵지는 않다. 

그냥 에라토스테네스의 체가 더 익숙해서 좋아할 뿐.. 

예전에 직접 시간을 측정해본 결과로는 에라토스테네스의 체가 유리할 거라고 생각한 상황에서도 크게 빠르지는 않더라.

 

    // 소수 구하는 함수
    public static boolean isPrimeNum(int n) {
        // 만약 인자 n이 0, 1이라면 false
        if (n==0 || n==1) return false;
        // 반복문
        for (int i=2; i*i<=n; i++) {
            //  i=2; i*i<=n; i++;
            if (n%i == 0) return false;
            //  if ( n % i == 0 ) return false;
            // 반복문 끝 ? return true;;
        }
        return true;
    }

 

 

아무튼 소수인지 체크하는 방법은 구했으니, 전체적으로 문제를 어떻게 풀어야할지 생각해봐야 한다.

나는 dfs 알고리즘을 이용해 풀기로 했다.

내가 작성한 야매 수도코드를 보자.

 

 

public class Main {
    static final int[] primeNums = {2,3,5,7};
    public static void main(String[] args) throws Exception {
        // 신기한 소수 구하기 (모든 자리 수가 소수다)
        // N의 최대값이 8 -> 즉 입력값의 최대 값이 9999만
        // 에라토스테네스의 체로 소수를 구할 경우 400mb(400000000byte)를 차지하는데 문제에서 제시하는 메모리 제한은 4MB
        // 따라서 매번 소수를 새롭게 구해야 한다.
        // 모든 경우의 수를 구하는 문제이므로 dfs

        // 자리수 N 입력 받기

        // dfs 탐색(인자 n, 자리수 N)
        // 인자 n은 소수 1,3,5,7로 직접 지정
    }

    // 소수 구하는 함수
    public static boolean isPrimeNum(int n) {
        // 만약 인자 n이 0, 1이라면 false
        if (n==0 || n==1) return false;
        // 반복문
        for (int i=2; i*i<=n; i++) {
            //  i=2; i*i<=n; i++;
            if (n%i == 0) return false;
            //  if ( n % i == 0 ) return false;
            // 반복문 끝 ? return true;;
        }
        return true;
    }

    // dfs 탐색
    public static void dfs(int num, int digits) {
        // if 자리수 N이 0이 된다면 소수인지 판별하고 맞으면 출력

        // 반복문
        // 1~10 반복하며 소수인지 체크하고 소수라면 digits는 -, num은 소수와 합쳐서 재귀
    }
}

 

사실 소수를 어떻게 구할지가 문제의 시작이자 끝이라서 크게 설명할 부분은 없다.

다만 내가 문제를 잘못 읽어서 수도 코드도 잘못 작성된 부분이 있는데, 바로 dfs 함수 안의 반복문이다.

 

문제에서 제시하기를 만약 4자리수라면 1자리수도 소수, 2자리수도 소수, 3자리수도 소수, 4자리수도 소수

그리고 추가적으로 1+2자리수도 소수, 1+2+3자리수도 소수 이런 조건을 만족해야 하는데

 

나는 문제를 똑바로 읽지 않고 그냥 각 자리수가 소수고 합치면 소수가 되는 경우로 답을 구해서 코드를 고쳐써야 했다.

해당 부분만 신경써서 직접 문제를 풀어보자

정답은 밑으로

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

public class Main {
    static final int[] primeNums = {2,3,5,7};
    public static void main(String[] args) throws Exception {
        // 신기한 소수 구하기 (모든 자리 수가 소수다)
        // N의 최대값이 8 -> 즉 입력값의 최대 값이 9999만
        // 에라토스테네스의 체로 소수를 구할 경우 400mb(400000000byte)를 차지하는데 문제에서 제시하는 메모리 제한은 4MB
        // 따라서 매번 소수를 새롭게 구해야 한다.// 모든 경우의 수를 구하는 문제이므로 dfs
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        // 자리수 N 입력 받기
        int N = Integer.parseInt(br.readLine());
 
        // dfs 탐색(인자 n, 자리수 N)
        // 인자 n은 소수 1,3,5,7로 직접 지정
        for (int i = 0; i< primeNums.length; i++) {
            dfs(primeNums[i], N-1);
        }
    }
 
    // 소수 구하는 함수
    public static boolean isPrimeNum(int n) {
        // 만약 인자 n이 0, 1이라면 false
        if (n==0 || n==1) return false;
        // 반복문
        for (int i=2; i*i<=n; i++) {
            //  i=2; i*i<=n; i++;
            if (n%i == 0) return false;
            //  if ( n % i == 0 ) return false;
            // 반복문 끝 ? return true;;
        }
        return true;
    }
 
    // dfs 탐색
    public static void dfs(int num, int digits) {
        // if 자리수 N이 0이 된다면 소수인지 판별하고 맞으면 출력
        if (digits == 0) {
            if (isPrimeNum(num)) {
                System.out.println(num);
            }
            return;
        }
 
        // 반복문
        for (int i=0; i< 10; i++) {
            int temp = num * 10 + i;
            if (isPrimeNum(temp)) {
                dfs(num*10+i, digits-1);
            }
        }
    }
}