[Baekjoon] 2023번: 신기한 소수

https://www.acmicpc.net/problem/2023

2023번: 신기한 소수

문제 설명

7331과 같이 7331도 소수, 733도 소수, 73도 소수, 7도 소수인 수를 신기한 소수라고 한다. 자릿수가 주어졌을 때 해당 자릿수의 신기한 소수를 모두 찾아내 오름차순으로 출력하는 프로그램을 작성하면 된다.

자릿수 N은 1 이상, 8 이하이다.

풀이 방법 1. 나의 풀이 - 통과

코드로 보는 편이 빨라 코드와 주석으로 설명하겠다.

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        
        // 주어진 자릿수의 최솟값은 10의 N-1승이다.
        // 또한 최댓값은 10의 N승이다.
        int MIN = (int)(Math.pow(10, N - 1));
        int MAX = (int)(Math.pow(10, N));
        
        StringBuilder sb = new StringBuilder();
        // 1은 소수가 아니므로 시작하는 값은 2로 시작한다.
        for (int i = MIN * 2; i < MAX; i++) {
            // 신기한 소수인지 체크하기 위한 변수이다.
            boolean isStrange = true;
            for (int j = N; j > 0; j--) {
                // 몫을 구하는데 첫째 짜리부터 구해나가기 시작한다.
                int mok = i / (int) Math.pow(10, j - 1);
                // 소수인지 판별한다.
                boolean result = isPrime(mok);
                // 소수가 아니라면 바로 반복을 종료한다.
                if (result == false) {
                    isStrange = false;
                    break;
                }
            }
            // 소수라면 출력 버퍼에 저장해 놓는다.
            if (isStrange) sb.append(i).append("\n");
        }
        
        System.out.print(sb);
    }
    
    private static boolean isPrime(int num) {
        if (num != 2 && num % 2 == 0) return false;
        
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

이렇게 풀고 다른 정답을 확인하러 채점 현황을 들어가보니 대부분의 정답은 시간이 140ms 내외였다. 어떻게 풀었나 코드를 확인해보았고 훨씬 더 효율적으로 풀 수 있는 방법이 더 있었다는 걸 깨달았다.

풀이 방법 2. 효율적인 풀이

1. 범위 제한

소수의 특징 중 대표적인 것은 2를 제외한 소수는 모두 홀수라는 것이다. 따라서 내 풀이처럼 2로 시작하는 수부터 모든 경우를 따지는 게 아니라 2, 3, 5, 7을 첫째 자리 수로 가지는 범위만 탐색하도록 알고리즘을 짤 수 있었다.

class Main {
    public static void main(String[] args) throws IOException {
    
        // ...
    
        judgeInterestingPrime(2, 1)
        judgeInterestingPrime(3, 1)
        judgeInterestingPrime(5, 1)
        judgeInterestingPrime(7, 1)
    }
    
    private static void judgeInterestingPrime(int num, int digit) {
        // ...
    }
}

2. 재귀

만약 num으로 넘어온 수가 소수라면 이제 N 자리수까지 가기 위해 재귀를 활용할 수 있다.

private static void judgeInterestingPrime(int num, int digit) {
    // 자릿수가 N까지 왔다면
    if (digit == N) {
        // num이 소수라면
        if(isPrime(num)) { // 출력한다.
            System.out.println(num);
        }
        return;
    }
    
    // 자릿수가 N까지 오지 않았다면 현재 자릿수에서 소수를 찾는다.
    // 짝수는 어차피 안 되므로 1부터 9까지 2씩 늘려간다.
    // 1부터 하는 이유는 31과 같은 소수도 있기 때문이다.
    for (int i = 1; i <= 9; i += 2) {
        int next = num * 10 + i;

        if (isPrime(next)) {
            judgeInterestingPrime(next, digit + 1);
        }
    }
}

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

전체 코드는 다음과 같다.

import java.io.*;

class Main {
    
    static int N;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
    
        judgeInterestingPrime(2, 1);
        judgeInterestingPrime(3, 1);
        judgeInterestingPrime(5, 1);
        judgeInterestingPrime(7, 1);
    }
    
    private static void judgeInterestingPrime(int num, int digit) {
        if (digit == N) {
            if(isPrime(num)) {
                System.out.println(num);
            }
            return;
        }
    
        for (int i = 1; i <= 9; i += 2) {
            int next = num * 10 + i;
            
            if (isPrime(next)) {
                judgeInterestingPrime(next, digit + 1);
            }
        }
    }

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

소요 시간이 거의 40배가 줄어든 것을 확인할 수 있다.