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

문제

풀이

N^2는 시간초과가 나기때문에 Brute Force로 풀 수 없는 문제이다.

• 정렬을 한 뒤 O(NlogN)
• for문을 돌면서 이분탐색을 하면 O(N * logN)
O(NlogN) 시간복잡도로 풀 수 있다.

1. 오름차순으로 정렬
   -99 -2 -1 4 98
2. for문을 돌면서 선택된 수의 오른쪽 부분을 -선택된 수로 이분탐색한다
   만약 -99 차례라면 99의 수와 가장 가까운 수를 탐색 98
3. 차이값이 가장 작은 수를 출력

코드

static int lower_bound(int[] A, int L, int R, int X) {
        // A[L..R] 에서 X 이상의 수 중 제일 왼쪽(작은 값) 인덱스를 return 하는 함수
        // 그런게 없다면 R을 return

        int res = R;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (A[mid] >= X) { // X가 작으니깐 작은 구간 다시 봄
                res = mid;
                R = mid - 1;
            } else { // X가 크니깐 큰 구간 다시 봄
                L = mid + 1;
            }
        }
        return res;
    }

lower_bound는 X와 가장 가까운 수의 index를 return하는 함수

• int[] A : 탐색하는 배열
• int L : 탐색하는 부분의 제일 왼쪽 index
• int R : 탐색하는 부분의 제일 오른쪽 index
• int X : 탐색해야하는 숫자

static void pro() {
		//정렬
        Arrays.sort(A, 1, N + 1);

        int best_sum = Integer.MAX_VALUE;
        int v1 = 0, v2 = 0;
        for (int left = 1; left <= N - 1; left++) {
            // A[left] 용액을 쓸 것이다. 고로 -A[left]와 가장 가까운 용액을 자신의 오른쪽 구간에서 찾자
            int res = lower_bound(A, left + 1, N, -A[left]);

            // A[res - 1] 와 A[res] 중에 A[left]와 섞었을 때 정보를 정답에 갱신
			// res - 1
            if (left + 1 <= res - 1 && res - 1 <= N && Math.abs(A[res - 1] + A[left]) < best_sum) {
                best_sum = Math.abs(A[res - 1] + A[left]);
                v1 = A[left];
                v2 = A[res - 1];
            }
			// res
            if (left + 1 <= res && res <= N && Math.abs(A[res] + A[left]) < best_sum) {
                best_sum = Math.abs(A[res] + A[left]);
                v1 = A[left];
                v2 = A[res];
	        }
        }
		// 정답 출력
        sb.append(v1).append(' ').append(v2);
        System.out.println(sb);
    }

그렇게 찾은 index의 수 또는 index - 1의 수가 정답이므로 두 가지의 경우 모두 계산하여 정답을 갱신

전체코드

/*
(이분탐색)
두 용액

A[left]를 정했을 때, -A[left]와 가장 가까운 걸 빨리 찾자!

정렬했을 때 이득
1. 이분 탐색 사용 가능
2. 가장 가까운 원소를 빠르게 찾기 가능

 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static StringBuilder sb = new StringBuilder();
    static int N;
    static int[] A;

    public static void input() {
        FastReader fr = new FastReader();
        N = fr.nextInt();
        A = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = fr.nextInt();
        }
    }

    static int lower_bound(int[] A, int L, int R, int X) {
        // A[L..R] 에서 X 이상의 수 중 제일 왼쪽(작은 값) 인덱스를 return 하는 함수
        // 그런게 없다면 R을 return

        int res = R;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (A[mid] >= X) { // X가 작으니깐 작은 구간 다시 봄
                res = mid;
                R = mid - 1;
            } else { // X가 크니깐 큰 구간 다시 봄
                L = mid + 1;
            }
        }
        return res;
    }

    static void pro() {
		//정렬
        Arrays.sort(A, 1, N + 1);

        int best_sum = Integer.MAX_VALUE;
        int v1 = 0, v2 = 0;
        for (int left = 1; left <= N - 1; left++) {
            // A[left] 용액을 쓸 것이다. 고로 -A[left]와 가장 가까운 용액을 자신의 오른쪽 구간에서 찾자
            int res = lower_bound(A, left + 1, N, -A[left]);

            // A[res - 1] 와 A[res] 중에 A[left]와 섞었을 때 정보를 정답에 갱신
			// res - 1
            if (left + 1 <= res - 1 && res - 1 <= N && Math.abs(A[res - 1] + A[left]) < best_sum) {
                best_sum = Math.abs(A[res - 1] + A[left]);
                v1 = A[left];
                v2 = A[res - 1];
            }
			// res
            if (left + 1 <= res && res <= N && Math.abs(A[res] + A[left]) < best_sum) {
                best_sum = Math.abs(A[res] + A[left]);
                v1 = A[left];
                v2 = A[res];
	        }
        }
		// 정답 출력
        sb.append(v1).append(' ').append(v2);
        System.out.println(sb);
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        Double nextDouble(){
            return Double.parseDouble(next());
        }

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            } catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}

느낀점

배열을 정렬하면 얻을 수 있는 이점을 생각하자
수가 커지면 이분탐색 혹은 누적합