[백준] 9202번. 골드바흐의 추측(JAVA)

문제

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

---

풀이(22분)

import java.awt.Point;
import java.util.*;
import java.io.*;

public class Main{

    static ArrayList<Integer> prime = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        isPrime(10000); // 10000까지의 소수 모두 찾아두기.
        int n = Integer.parseInt(br.readLine());

        System.out.println(prime.size());
        for(int i = 0; i < n; i++){
            int test = Integer.parseInt(br.readLine());
            int[] answer = find(test);
            System.out.println(answer[0] + " " + answer[1]);
        }
    }

    public static int[] find(int n){
        int start = 0;
        int end = prime.size() - 1;
        int mid = 0;
        while(start <= end){
            mid = (start + end) / 2;
            if(n/2 == prime.get(mid)){
                break;
            }
            if(n/2 < prime.get(mid)){
                end = mid - 1;
                continue;
            }
            start = mid + 1;
            continue;
        }
        start = mid;
        end = mid;

        while(start >= 0 && end < prime.size()){
            int left = prime.get(start);
            int right = prime.get(end);
            if(left + right == n){
                return new int[]{left, right};
            }
            if(left + right > n){
                start--;
                continue;
            }
            end++;
        }
        return new int[]{};
    }

    public static void isPrime(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);

        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // prime 리스트에 소수 추가
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                prime.add(i);
            }
        }
    }

}

 

먼저 n이 10000까지라는 제한이 있으므로 10000까지의 소수를 모두 찾아준다.

이후 과정은 다음과 같다.

 

1. 소수를 어디서부터 찾을지를 정한다. find메서드의 start = mid, end = mid까지의 부분으로 이분 탐색을 통하여 정수 n의 가장 가까운 위치를 찾는다.

-> 이렇게 해야 차이가 크지 않은 두 소수를 효율적으로 찾을 수 있을 것이라고 판단했다.

2. start와 end로 구한 left, right값을 통하여 정답을 찾아간다.

2-1. 값이 됐다면 반환하면 된다.

2-2. 값이 크다면 start를 한 칸 앞으로 땡긴다.(1번의 과정을 통해 이미 end는 최하범위까지 내려와 있는 상태라고 생각하면 된다.)

2-3. 값이 작다면 end를 한 칸 뒤로 미루낟.(1번의 과정을 통해 이미 start는 최대범위까지 올라와있는 상태이다.)

3. 이 과정을 반복하며 답을 찾는다.

 

추가적으로 isPrime에서 리스트에 추가하는 것을 로직상 분리하지 않고, 배열 체크 시 동시에 진행하여 문제가 있었다.

이미 알고있는 알고리즘을 사용할 때 그 로직을 한 번씩은 더 생각해 보고 짜는 것이 중요하다고 느꼈다.