[백준 2023] 신기한 소수 (JAVA)

백준 2023번 문제  - 신기한 소수

2023번: 신기한 소수

---

문제 분석

 

• 자리수가 입력되면 해당 자리 수 중에서 다음 조건을 만족하는 수(신기한 소수)들을 출력해라
  • N번자리부터 오른쪽으로 0부터 N-1까지 숫자를 같이 봤을 때 모든 수가 다 소수인 수
    ex) N = 4 | 주어진 숫자 = 2333 일 때 해당 수는 신기한 소수에 포함 (다음 표 참고)

i	N부터 i까지 오른 쪽 숫자	소수 판별
0	2	O
1	23	O
2	233	O
3	2333	O

 

---

해결 키 포인트

 

• DFS(깊이 우선 탐색) 개념 파악 : 사실 본 포스트 코드는 깊이 우선 탐색을 잘 사용하진 않음
• 소수 개념 파악
  - 소수 : 해당 수가 1과 자기 자신으로만 나누어 떨어지는 수 (1은 미포함)
• 속도를 줄이기 위해, i 자리 수까지의 수가 소수가 아닐 경우는 해당 자릿 수를 증가시켜 변경
  ex) 200 : 2 (소수 O) - 20 (소수 X) → 다음 확인할 수는 201이 아닌 210 !

---

깊이 우선 탐색(DFS)

 

그래프 완전 탐색 기번 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

 

깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야 한다.

 

깊이 우선 탐색의 핵심 이론

 

• 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요
• 그래프는 인접 리스트로 표현
• DFS의 탐색 방식은 후입 선출 특성을 가짐 ( 재귀함수 사용 많음 / 스택도 사용 )

 

알고리즘

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

 

Do It! 알고리즘 코딩 테스트

 

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입 (이를 모든 정점을 다한다)

 

Do It! 알고리즘 코딩 테스트

 

만약 스택에 노드가 없으면, 방문하지 않은 정점을 알아내, 스택에 삽입하고 다시 2번 단계를 반복한다.

---

코드

import java.io.*;

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

        // N 입력
        int N = Integer.parseInt(br.readLine());
        br.close();

        // 해당 자리수의 가장 작은 값
        int minNum = 1;
        for (int i = 1; i < N; i++) {
            minNum *= 10;
        }
        // 해당 자리수의 가장 큰 값 다음 값
        int maxNum = minNum * 10;

        // 현재 수
        int currentNum = minNum;

        // max 수까지 반복
        while (currentNum < maxNum) {
            int[] Nnum = new int[N];
            Nnum[N - 1] = currentNum / minNum;

            // N번째 자리 수가 소수여야 함 (2,3,5,7)
            if (checkPrimeNumber(Nnum[N - 1])) {
                // 수가 두자리 이상일 경우
                if (N >= 2) {
                    int checkNum = minNum / 10;

                    int i = N-2;
                    // 각 자리 수의 값 알아내기
                    for (i=N-2; i>=0; i--) {
                            Nnum[i] = currentNum % (checkNum * 10) / (checkNum);
                            int num = currentNum / checkNum;

                        // 해당 자리 수까지 값이 소수인지 판별 | 아니라면 해당 수는 안되는 수이므로 해당 자리수 증가시켜 수 변경
                        if (!checkPrimeNumber(num)) {
                            currentNum = checkNum * (num + 1);
                            break;
                        }

                        // 해당 자리수까지 소수라면 다음 자리수 확인
                        checkNum /= 10;
                    }

                    // 지금 확인 자리수가 -1이면 해당 조건을 만족하는 소수이므로 출력 및 수 변경
                    if (i == -1) {
                        bw.write(currentNum + "\n");
                        currentNum++;
                    }

                // 한자리 수일 경우, 해당 수가 소수이면 소수이므로 출력
                } else {
                    bw.write(currentNum + "\n");
                    currentNum++;
                }

            }
            // N번째 자리 수가 소수가 아니라면 해당 자리수 숫자 변경
            else {
                currentNum = minNum * (Nnum[N - 1] + 1);
            }
        }

        // 출력
        bw.flush();
        bw.close();
    }

    // 소수인지 알아내는 함수
    public static boolean checkPrimeNumber(int n) {
        if(n == 1) return false;
        for(int i=2;i<n-1;i++) {
            if(n % i == 0) {
                return false;
            }
        }

        return true;
    }
}