[백준] 9020번 : 골드바흐의 추측 - JAVA[자바]

9020번 : 골드바흐의 추측

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

테스트 케이스의 개수만큼 Queue에 n의 값을 offer 해주고
처음에 처리할 값을 미리 initialization 하고 버퍼에 입력해주고 다음 값을 poll 을 했기 때문에 시간복잡도를 O(N^2)에서 O(N)으로 줄일 수 있다.

중요한 것은 j = n / 2 인데 문제에 골드바흐의 수가 여러 개 -> 차이가 가장 작은 것을 출력
n / 2 근처에서 값을 찾으면 차이를 최소화 할 수 있다.

에라토스테네스의 체를 루프 시작 전에 구현하고 사용하는 것도 시간복잡도를 줄일 수 있다.

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

public class Main {
    public static boolean[] isPrimeNumber = new boolean[10001];
    public static void main(String[] args) throws IOException {
        BufferedReader br   = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw   = new BufferedWriter(new OutputStreamWriter(System.out));
        Queue<Integer> temp = new LinkedList<>();

        createFunc();//에라토스테네스의 체 create 함수

        int $test_case = Integer.parseInt(br.readLine());

        for(int i = 0; i < $test_case; i++) {temp.offer(Integer.parseInt(br.readLine()));}
        int n = temp.poll();

        for(int j = n/2; j < 10001; j++) {
            if (isPrimeNumber[j] && isPrimeNumber[n-j] ) {
                bw.write(String.valueOf(Math.min(j, n-j) + " " + Math.max(j, n-j) + "\n"));
                if (temp.isEmpty()) break;
                n = temp.poll();
                j = (n / 2) - 1;
            }
        }
        br.close();
        bw.flush();
        bw.close();
        return;
    }
    public static void createFunc() {
        for (int i = 2; i < 10001; i++) {
            isPrimeNumber[i] = true;
        }//0과 1은 소수가 아니므로 직접 처리
        isPrimeNumber[0] = false;
        isPrimeNumber[1] = false;

        for (int j = 2; j * j <= 10000; j++) {
            if (j != 4) {
                for (int k = 2; j * k <= 10000; k++) {
                    isPrimeNumber[j * k] = false;
                }
            }
        }
    }
}

> Math.Min(), Math.Max() 귀찮아서 쓰긴 했는데 더 좋은 표현식이 있을 것 같다. 생각하긴 싫고