[백준] 2023 : 신기한 소수 - Java

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

코드

public class 백준_2023_신기한소수 {

    static int n;
    static int N;
    static boolean[] data;
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        N = (int) Math.pow(10, n);
        data = new boolean[N+1];
        // true -> 소수, false -> 소수 아님
        Arrays.fill(data, true);  // 모든 수가 소수라고 판단
        data[0] = false;
        data[1] = false;

        primeNumber();  // 소수처리 진행

        for (int num = N/10; num < N; num++) {   // N자리 수들 중 소수들 확인
            if (data[num] == true && checkPrime(num)) {
                System.out.println(num);
            }
        }
    }

    public static void primeNumber() {
        for (int num = 2; num <= (int) Math.sqrt(N); num++) {
            if (data[num] == true) {
                int j = 2;
                while (num * j <= N) {
                    data[num*j] = false;  // 배수는 모두 false 처리.
                    j += 1;
                }
            }
        }
    }

    public static boolean checkPrime(int num) {
        while (num > 0) {
            if (!data[num]) {  // 소수가 아니라면 false 반환
                return false;
            }
            num = num/10;
        }
        return true;
    }
}

코멘트

해당 문제는 자리수가 매우 크기 때문에 에라토스테네스의 체 방식으로 소수를 구한 후 해당 범위를 체크하면 시간 초과 및 메모리 초과가 발생한다. 따라서 시간과 메모리를 적게 드는 방식으로 풀어야 한다.
-> DFS와 소수의 특징을 이용하면 시간 초과 및 메모리 초과를 방지할 수 있다.

• 모든 소수를 체크하는 것이 아닌, 한 자리의 소수를 각 자리수에 추가하면서 전체 수가 소수인지를 체크하는 것이 더 효과적.

즉 초기값 세팅은 애초에 첫째자리가 2,3,5,7인 경우만 올 수 있음. 이걸 생각하고 접근했어야 함.

내 첫번째 코드는 전부 에라토스테네스의 체로 문제를 해결했다.

이게 아닌 DFS로 푼 코드는...
두번째 코드이다.

package 알고리즘_수업이후_과제.세번째주차_알고리즘.백준;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 백준_2023_신기한소수 {

    static int n;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        DFS(1, 2);
        DFS(1, 3);
        DFS(1, 5);
        DFS(1, 7);
        System.out.println(sb);
    }

    public static void DFS(int L, int num) { // 자릿수, 현재 숫자
        if (L == n) { // n번째 자리 수 도착하면 이제 해당 수가 '신기한 소수'임을 확인가능
            System.out.println(num);
        } else {
            for (int i = 1; i <= 9; i+=2) {  // 애초에 짝수도 소수가 될 수 없음.
                int nextNum = num*10 + i;
                // 해당 수 소수 판별
                if (isPrimeNum(nextNum)) {
                    DFS(L + 1, nextNum);  // 소수인 경우만 다음 단계로 이동.
                }
            }
        }
    }

    public static boolean isPrimeNum(int num) {
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
            if(num % i == 0)
                return false;
        }
        return true;
    }
}

메모리, 시간초과 생각해야한다.