[2023-04-10] 백준 2023 신기한 소수

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

2023번: 신기한 소수

 

성능 요약

메모리: 15972 KB, 시간: 512 ms

분류

수학, 정수론, 백트래킹, 소수 판정

문제 설명

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

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

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

입력

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

출력

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

 

---

해결 과정

먼저 DFS와 에라토스테네스의 체를 이용해서 문제를 풀어보려 시도했다. 에라토스테네스의 체는 O(Nlog(logN))의 시간 복잡도를 갖는 대표적인 소수 구하는 방법 중 하나이다.

 

다음과 같은 과정을 거쳐 시도를 해보았다.

 

1) 2,3,5,7을 스택에 먼저 추가한다.

2) 10^(입력받은 값)만큼의 배열 공간을 선언해 소수를 구분, 저장해준다.

3) 스택이 비기 전까지 다음의 반복문을 반복한다.

 3-1) stack.pop을 한 후 자릿수가 입력받은 자릿수인지 검사한다.

  3-1-true) BufferedWriter에 넣어준다.

 3-2) 해당 값에 10을 곱하고 0~9까지 더해주며 값이 소수인지 체크한다.

  3-2-true) stack에 소수를 추가한다.

 

다만 해당 방법으로 해결하려 했을 시 시간 초과는 발생하지 않으나 메모리 초과 오류를 발생시켰다.

 

메모리 제한은 4MB로 boolean타입의 변수가 4,000,000 생성될 수 있는 크기이다. 하지만 내가 푼 방식은 최대 100,000,000개의 boolean 타입 변수를 생성하는 코드이므로 메모리 오류가 발생했다.

 

이보다 약간 느리지만 시간 범위 내에서 해결할 수 있는 방법은 먼저 소수를 찾은 후 비교하는 방식이 아닌, 들어온 수가 소수인지 아닌지 판별하는 방식이었다. 2부터 (해당 값/2)까지인 i를 해당 값과 나누었을 때 나누어 떨어지는 지를 판단하여 반환해주는 함수를 생성해 해결하였다.

---

코드

import java.io.*;
import java.util.*;

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));


        int N = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();

        //2,3,5,7 추가하고 시작
        stack.push(7); stack.push(5);
        stack.push(3); stack.push(2);

        int h = (int) Math.pow(10, N);
        //arr = new boolean[h];
        //arr[0] = true; arr[1] = true;
        //stack이 빌때까지 반복
        while(!stack.isEmpty()) {
            int a = stack.pop();
            //a가 해당 자릿값 숫자라면 출력
            if((a % (Math.pow(10, N-1))) != a) bw.write(a + "\n");
            a *= 10;
            for(int i = 9; i >= 0; i--) {
                int k = a + i;
                //소수이면 추가
                if((k < h) && Decimal(k)) stack.push(k);
            }
        }
        bw.flush();
        bw.close();
    }

    private static boolean Decimal(int k) {
        for(int i = 2; i <= k / 2; i++) {
            if(k % i == 0) return false;
        }
        return true;
    }

}