[백준] 2023 신기한 소수 - 브루트포스 + 소수 판정 JAVA

https://www.acmicpc.net/board/view/75999

글 읽기 - 메모리초과 또는 시간초과 해결방법

코드설명

브루트포스와 소수판정 문제입니다.

 

처음에는 에라토스테네스 체를 구현하여 진행했지만, 메모리 초과가 납니다.

public static int MAX = 100000000;
public static boolean[] primeNumber = new boolean[MAX]; //소수저장DP

//에라토스테네스의 채
for(int i=2;i<MAX;i++) { //2의 배수, 3의 배수, 4의 배수 ...
    if(primeNumber[i] == false) { //처음 시작 숫자가 소수라면 검사하지 않습니다. false 일경우 소수로 판단합니다. 에라토스테네스의 체는 기본적으로 처음에 모든 수를 소수로 판단하고, 나눠지는경우 true로 바꾸어 소수가 아닌것으로 판단합니다.
        for(int j=2*i; j<MAX;j+=i) { //처음에는 2의 배수로 시작하며, i로 해당 숫자를 나눌 수 있는지 확인합니다. 
            primeNumber[j] = true;
        }	
    }
}

int 자료형의 메모리크기는 4byte 입니다.

현재 MAX값은 100000000 이므로 4 * 100000000 입니다.  즉 400MB 입니다..

만약 메모리 제한이 512 MB였다면 통과였겠지만 문제에서는 메모리 제한이 4 MB이므로 곧바로 메모리 초과가 납니다.

 

처음에 N을 받고서 N =4 라면, 1000 ~ 9999 까지의 숫자만 가능하므로 1000 ~ 10000 의 숫자를 구한뒤 해당 구간을 반복문을 돌도록 설정했습니다.

7331 을 받았을 떄는 7331 -> 733 -> 73 -> 7 이런식으로 브루트포스를 진행하여, 한개라도 소수가 아니라면 신기한 소수가 아니므로 종료시켰습니다.

 

시간초과를 벗어나기 위해서는, 모든 숫자의 소수여부를 판별한뒤 신기한 소수인지 아는것이 아닌,

처음부터 만들어가면서 한번이라도 소수가 아니라면 바로 중단하는 로직을 짜야합니다.

 

아래의 코드에서 보이듯이 i=1 ~  i < 10 까지 모든 숫자를 만들어갑니다. 그러면서 해당 숫자가 primeNumber일때만 다음 숫자를 만들어갑니다. 만약에 다음숫자가 primeNumber가 아닐경우에는 simulate가 발생하지 않습니다.

public static void simulate(int num, int level) {
    if(level == 0) { //만약 level 자리수를 모두 사용했따면, 출력합니다.
        System.out.println(num);
    }
    for(int i=1; i<10; i++) {
        int numTemp = 10 * num + i;
        if( level > 0 && isPrime(numTemp)) {
            simulate(numTemp, level -1);
        }
    }
}

public static boolean isPrime(int num) {
    if(num < 2) return false; //만약 숫자가 1이거나 0 이면 소수가 아닙니다.
    for(int i=2; i<=Math.sqrt(num); i++) { // Math.sqrt 대신 i*i <= 도 가능합니다.
        if(num % i == 0) {
            return false; // num 숫자가 i의 배수이면 소수가 아닙니다.
        }
    }
    return true; //통과한다면 소수입니다.
}

 

코드

메모리 절약한 정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	simulate(0, N);
    }
	
	public static void simulate(int num, int level) {
		if(level == 0) { //만약 level 자리수를 모두 사용했따면, 출력합니다.
			System.out.println(num);
		}
		for(int i=1; i<10; i++) {
			int numTemp = 10 * num + i;
			if( level > 0 && isPrime(numTemp)) {
				simulate(numTemp, level -1);
			}
		}
	}
	
	public static boolean isPrime(int num) {
		if(num < 2) return false; //만약 숫자가 1이거나 0 이면 소수가 아닙니다.
		for(int i=2; i<=Math.sqrt(num); i++) { // Math.sqrt 대신 i*i <= 도 가능합니다.
			if(num % i == 0) {
				return false; // num 숫자가 i의 배수이면 소수가 아닙니다.
			}
		}
		return true; //통과한다면 소수입니다.
	}
}

 

처음에 메모리초과 코드, 에라토스테네스의 체를 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static ArrayList<Long> answerArr = new ArrayList<>();
	public static int MAX = 100000000;
	public static boolean[] primeNumber = new boolean[MAX]; //소수저장DP
	public static boolean weiredNumberFlag = false;
	public static int startNum = 1, endNum = 10;
	
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	for(int i=0;i<N-1;i++) {
    		startNum *= 10;
    		endNum *= 10;
    	}
    	//에라토스테네스의 채
    	for(int i=2;i<MAX;i++) { //2의 배수, 3의 배수, 4의 배수 ...
    		if(primeNumber[i] == false) { //처음 시작 숫자가 소수라면 검사하지 않습니다. false 일경우 소수로 판단합니다. 에라토스테네스의 체는 기본적으로 처음에 모든 수를 소수로 판단하고, 나눠지는경우 true로 바꾸어 소수가 아닌것으로 판단합니다.
    			for(int j=2*i; j<MAX;j+=i) { //처음에는 2의 배수로 시작하며, i로 해당 숫자를 나눌 수 있는지 확인합니다. 
    				primeNumber[j] = true;
        		}	
    		}
    	}
        
    	//각 자리수에 맞게 처리해야합니다.
    	for(int i=startNum; i<endNum;i++) {
    		weiredNumberFlag = true;
    		simulate(i);
    		if(weiredNumberFlag == true) {
    			System.out.println(i);
    		}
    	}
    	
    }
	
	public static void simulate(int num) {
		if(num == 0 || weiredNumberFlag == false) { //만약 num이 0이거나 이미 신기한수가 아니라면  중단시켜야합니다.
			return ;
		}
		
		if(primeNumber[num] == true) {
			weiredNumberFlag = false;
		}
		simulate(num / 10);
		
		
	}
}