[백준 2023번/JAVA] 신기한 소수

문제

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

2023번: 신기한 소수

N을 입력받고 N의자리수 중 신기한 소수에 해당하면 출력한다.

신기한 소수란? 예) 373은 신기한 소수다. 3도 소수, 37도 소수, 373도 소수이기 때문.

뒷자리부터 검사 (N자리수에 해당하는 모든 숫자 검사) - 시간 초과

처음에는 N의 자리에 해당하는 모든 수를 신기한 소수인지 검사하는 코드를 짰다.

1. N의자리 숫자 중 가장 작은 수가 소수인지 확인
2. 소수이면 (숫자/10)이 소수인지 확인 -> 일의자리수가 될 때까지 반복

예) N=3 : 233은 소수 -> 23은 소수 -> 2는 소수 -> 신기한 소수에 해당
(100~999 중 소수에 해당하는 수가 모두 검사 대상이 됨)

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

public class Main {    
    static String result;

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

        int num = 1;
        int endNum = 1;
        int N = Integer.parseInt(br.readLine());

        //검사를 시작할 숫자
        if(N!=1){
            for(int i=1; i<N; i++)
                num *= 10;
        }

        for(int i=1; i<=N; i++)
            endNum *= 10;

        for(int i=num; i<endNum; i++){        
            isPrimeNum(i);
            if(result=="true")
                sb.append(i+"\n");
        }
        bw.write(sb+" ");
        bw.close();            
    }

    static void isPrimeNum(int tmp) {    
        result = "false";

        //1은 소수가 아님
        if(tmp==1) {
            return;
        }

        //2부터 tmp-1 사이의 숫자로 나눠진다면 소수가 아님
        for(int i=2; i<tmp; i++) {
            if(tmp%i==0) {
                return;
            }
        }

        tmp /= 10;

        if(tmp==2 || tmp==3 || tmp==5 || tmp==7) {
            result = "true";
        }else {
            isPrimeNum(tmp);
        }
    }
}

그런데 이런 식으로 코드를 짜면 시간 초과가 뜬다.

 

최악의 경우(N=8) 10,000,000~99,999,999를 모두 검사한 후 소수를 걸러내고(약 천만 번 연산) 그 중 소수로 판별된 숫자만큼 또 재귀를 진행한다.

 

걸러진 소수의 숫자만큼 연산의 횟수가 계속 제곱되기 때문에 주어진 시간(2억번) 내로 연산을 끝낼 수 없다.

앞자리부터 검사 + 맨 앞자리는 2, 3, 5, 7 배열에서 가져오기 

앞자리부터 자릿수를 늘려가며 검사하는 방법이다.

앞자리부터 소수인지 판별하므로 검사할 숫자의 개수가 대폭 줄어든다.

1. 가장 앞자리수가 소수인지 확인
2. 뒤에 1~9를 붙여 소수인지 확인 -> N의 자리가 될 때까지 반복

예) N=3 : 2는 소수 -> 23은 소수 -> 233은 소수 -> 신기한 소수에 해당

 

어차피 일의자리 중에 소수는 2, 3, 5, 7밖에 없으므로 그냥 맨 첫 번째 자리가 소수인지 판별하는 과정을 없앴다.

그래서 N의 자리 검사 시 num*10+i 과정을 N-1번 반복하도록 했다.

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

public class Main {    
    static StringBuilder sb = new StringBuilder();    

    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());
        int[] arr = {2, 3, 5, 7};

        for(int i=0; i<4; i++) {        
            recursive(arr[i], N-1);
        }
        bw.write(sb+" ");
        bw.close();

    }

    static void recursive(int num, int n) {    
        if(n==0) {
            if(isPrimeNum(num)) {
                sb.append(num).append("\n");
                return;                            
            }
        }

        for(int i=0; i<10; i++) {    
            int next = num*10+i;
            if(isPrimeNum(next))
                recursive(next, n-1);
        }

    }

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

이 코드에서 에라토스테네스의 체를 적용하면 더 효율적인 코드로 만들 수 있다.

앞자리부터 검사 + 에라토스테네스의 체 + 맨 앞자리는 2, 3, 5, 7 배열에서 가져오기

내가 짠 코드처럼 2~n-1을 다 돌며 약수존재 여부를 확인하는 것도 방법이겠지만 이 방법은 O(N)의 시간복잡도가 요구된다.

 

에라토스테네스의 체는 2~n^1/2까지만 약수 존재 여부를 확인해도 된다는 이론이다.

예를 들어 8이 소수인지 확인한다고 하자. 8 = 2*4 = 4*2이므로 8의 제곱근인 2.xxx기준으로 앞쪽에 약수가 있다면
대칭지점에 무조건 약수가 하나 더 있기 때문에, 뒤쪽은 굳이 확인할 필요없다는 뜻.

 

그러면 O(N^1/2)로 시간복잡도가 줄어든다.

 

*자바에서 숫자의 제곱근을 구하는 방법 : Math.sqrt()

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

public class Main {    
    static StringBuilder sb = new StringBuilder();    

    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());
        int[] arr = {2, 3, 5, 7};

        for(int i=0; i<4; i++) {        
            recursive(arr[i], N-1);
        }
        bw.write(sb+" ");
        bw.close();

    }

    static void recursive(int num, int n) {    
        if(n==0) {
            if(isPrimeNum(num)) {
                sb.append(num).append("\n");
                return;                            
            }
        }

        for(int i=0; i<10; i++) {    
            int next = num*10+i;
            if(isPrimeNum(next))
                recursive(next, n-1);
        }

    }

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

앞자리부터 검사 + 에라토스테네스의 체 + 맨 앞자리부터 isPrimeNum()으로 확인하기

연습하면서 혼자 다시 구현해봤는데 이번에는 맨 앞자리부터 for문을 돌렸다.

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

public class Main {	
	static StringBuilder sb = new StringBuilder();
	static int N;
	
	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 = Integer.parseInt(br.readLine());
		//맨처음숫자가 소수 -> true면 숫자*10+i가 소수인지 화긴
		for(int i=0; i<10; i++)
			recursive(i, 2);
		
		bw.write(sb+" ");
		bw.close();
		
	}
	
	static void recursive(int num, int n) {
		if(n>N) {
			if(isPrimeNum(num)) {
				sb.append(num+"\n");
				return;				
			}
		}
		
		if(isPrimeNum(num)) {
			for(int i=0; i<10; i++) {
				recursive(num*10+i, n+1);
			}
		}
	}
	
	static boolean isPrimeNum(int num) {
		if(num<2) {
			return false;
		}
		for(int i=2; i<=Math.sqrt(num); i++) {
			if(num%i==0) {
				return false;
			}
		}
		return true;
	}
}

 

1. 앞자리부터 검사 + 에라토스테네스의 체 + 맨 앞자리부터 isPrimeNum()으로 확인하기

2. 앞자리부터 검사 + 에라토스테네스의 체 + 맨 앞자리는 2, 3, 5, 7 배열에서 가져오기

3. 앞자리부터 검사 + 맨 앞자리는 2, 3, 5, 7 배열에서 가져오기

4. 뒷자리부터 검사 (N자리수에 해당하는 모든 숫자 검사)

• 약수 확인 범위를 제곱근으로 줄이기만 했는데 성능 차이가 엄청나다.
• 맨 앞자리를 2, 3, 5, 7로 지정하고 시작하니 시간이 단축되었다.

Note

• 재귀함수에서 num = num*10+i로 구현해서 정답이 잘못 출력되고 있었는데, 원인을 몰라서 시간을 많이 씀
• StringBuilder을 전역으로 한 번, main함수 내에 한 번 선언해서 출력 자체가 안 되고 있었는데 원인을 몰라 시간을 많이 씀
• 소수인지 판별하는 함수 자체를 재귀로 만들려고 시도하면서 시간을 많이 씀