[코딩테스트] 백준 2023 자바

백준 2023

백준 2023 문제

해당 문제는 일의 자리부터 n의 자리까지의 숫자가 모두 소수로 이루어진 수를 구하는 문제이다.

문제의 예시처럼 n이 4일 경우에 일의 자리 중에 소수인 2를 기준으로 2를 십의 자리로 갖는 수 중에 23이 소수이다.
그리고 23을 백의 자리, 십의 자리를 갖는 수 중에 233이 소수이다.
그리고 233을 천의 자리, 백의 자리, 십의 자리를 갖는 수 중에 2333이 소수이다. 그럼 출력하면 된다.

이런 식으로 2를 기준으로 네 자릿수(천의 자리)까지 깊이 우선 탐색을 하면서 출력을 하면 해당 문제를 풀 수 있고, 탐색 중 십의 자리나, 백의 자리에서 소수가 아닌 수는 넘어갈 수 있기 때문에 시간 복잡도도 줄일 수 있다.

import java.util.*;

public class Boj2023 {

    private static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 자릿수

        // 숫자 2, 3, 5, 7만 일의 자리의 소수이기 때문에 해당 수로 탐색 시작, 일의 자리 시작이므로 자릿수는 1
        dfs(2, 1);
        dfs(3, 1);
        dfs(5, 1);
        dfs(7, 1);
    }

    // dfs 구현
    private static void dfs(int num, int digit) {
        if (digit == n) { // 자릿수가 n이고
            if (isPrime(num)) { // num이 소수이면
                System.out.println(num); // num 출력
            }
            return; // 탐색 종료
        }

        for (int i = 1; i <= 9; i += 2) { // 짝수면 소수가 될 수 없기 때문에 홀수만 일의 자리에 추가
            if (isPrime(num * 10 + i)) { // 뒤에 붙는 수가 홀수이면서 소수일 때
                dfs(num * 10 + i, digit + 1); // 재귀 함수로 자릿수를 늘리면서 dfs 실행
            }
        }
    }

    // 소수 구하는 메서드
    private static boolean isPrime(int num) {
        for (int i = 2; i <= num / 2; i++) { // 2부터 num / 2까지 나누기
            if (num % i == 0) { // 나머지가 0이면 소수가 아님
                return false;
            }
        }
        return true; // 끝까지 나머지가 0이 아니면 소수
    }
}

문제 풀이

1. 자릿수 n을 입력 받는다.
2. 일의 자리 중에서 소수인 2, 3, 5, 7을 기준으로 깊이 우선 탐색을 하며 소수를 찾을 수 있도록 자릿수 1과 함께 전달하며 dfs()를 호출한다.
3. dfs()는 전달 받은 수의 자릿수가 n이며, 소수이면 출력하고 탐색을 종료한다. 소수가 아니면 그냥 탐색을 종료한다.
4. 전달 받은 수의 자릿수가 n이 아니면, 해당 수의 일의 자리에 홀수만 더하면서 더한 수가 소수인지 확인하고 소수이면 재귀 함수를 통해 자릿수를 늘리면서 dfs()를 실행하여 깊이 우선 탐색을 하며 소수를 찾도록 한다.
5. isPrime() 메서드는 입력된 수를 2부터 num / 2까지 나머지가 0이 아니면 소수이기 때문에 그것을 판별해준다.