9020. 골드바흐의 추측 (자바, Java)

 

맞추는건 어렵지 않은데, 시간제한이 있습니다.

 

첫번쨰 시도, 이클립스에서는 성공했지만, 시간초과로 실패했습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		
		
		for (int i=0; i<t; i++) {
			
			int n = Integer.parseInt(br.readLine());
			ArrayList<int[]> gold2 = new ArrayList<>();
			
			for (int j=0; primenumber().get(j)<n; j++) {
												
				for (int k=j; primenumber().get(k)<n; k++) {
										
					if (primenumber().get(j) + primenumber().get(k) == n) {
						
						int[] gold = new int[3];
						gold[0] = primenumber().get(k) - primenumber().get(j);
						gold[1] = primenumber().get(j);
						gold[2] = primenumber().get(k);						
						gold2.add(gold);
						
					}
					
				}
				
				
				
			}	// 골드바흐 파티션 구하기
			
			int min = gold2.get(0)[0];
			int count = 0;
			
			for (int j=0; j<gold2.size(); j++) {
								
				if ((min)>gold2.get(j)[0]) {
					
					min = gold2.get(j)[0];
					count = j;
					
				}
				
			}	// 골드바흐파티션 중 차이가 가장 작은값 구하기
			
			System.out.println(gold2.get(count)[1] + " " + gold2.get(count)[2]);
			
		}
		
	}
	
	public static ArrayList<Integer> primenumber() {
		
		ArrayList<Integer> p = new ArrayList<>();
		
		boolean pn[] = new boolean[10001];
		// pn이 false면 소수, true면 소수아님
		
		for (int i=0; i<=100; i++) {
			
			if (i <= 1) {
				
				pn[i] = true;
				continue;
				
			}
			
			for (int j=i*i; j<=10000; j+=i) {
				
				pn[j] = true;
				
			}
			
						
		}
		
		for (int i=0; i<pn.length; i++) {
			
			if (pn[i] == false) {
				
				p.add(i);
				
			}
			
		}
		
		return p;	
		
	}

}

 

실패요인 : n까지 이중구문을 통해, 시간복잡도 O(n^2)짜리를 사용하여 효율이 매우 떨어짐.

두번쨰 시도 : 구글링으로 새로이 힌트를 얻어 해결했습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		
		for (int i=0; i<t; i++) {
			
			int n = Integer.parseInt(br.readLine());
			int m = n/2;
			
			for (int j=0; j<m; j++) {
				
				if (primenumber()[(m-j)] == false && primenumber()[(m+j)] == false) {
					
					System.out.println((m-j) + " " + (m+j));
					break;
					
				}
				
			}
			
		}
					
		
	}
	
	public static boolean[] primenumber() {
				
		boolean pn[] = new boolean[10001];
		// pn이 false면 소수, true면 소수아님
		
		for (int i=0; i<=100; i++) {
			
			if (i <= 1) {
				
				pn[i] = true;
				continue;
				
			}
			
			for (int j=i*i; j<=10000; j+=i) {
				
				pn[j] = true;
				
			}
			
						
		}
				
		return pn;	
		
	}

}

이전 이중구문에서, 가운데인 n/2에서 1씩 증감해가며 해당 수들이 소수인지 판별하여 단일구문으로 좁혔습니다.