문제 접근

시간 제한은 1초다. 그런데, N은 갯수는 10만개다. 즉, 브루트 포스로는 안된다. 그렇다면 가장 적합한 방법은 NlogN이다. 그러면 우리는 문제의 본질을 이해하고 이 안에서 NlogN으로 해결할 수 있는 알고리즘을 떠올려야 한다.

• 음수 중 0에 가장 가까운 두 개를 더한 값
• 양수 중 0에 가장 가까운 두 개를 더한 값
• 음수 n1과 절댓값이 가장 가까운 양수 n2를 더한 값

이 값들 중 최솟값을 찾으면 된다.
사실 케이스1과 케이스2는 쉽다. O(1)안에 끝난다.
케이스3이 문제인데, 잘 생각해보면, 그냥 음수들 각각에 대해서 양수들 중 자신의 절댓값과 가까운 값을 이진탐색으로 찾으면 된다. 그러면, 모든 음수에 대해 순회하는데 O(NlongN) 이면 된다.

문제 풀이

lowerBound 코드가 잘 생각이 나질 않아 예전에 정리한 걸 참고했다. 시작은 배열 길이로 잡고, lowerBound의 반환은 mid를 하면 된다. (upperBound는 mid-1), 그리고 max값을 조정하는 과정에서 mid-1로 보내지 않는다. mid로 보낸다.

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

class Main {
    static int N;
    static ArrayList<Integer> plus = new ArrayList<>();
    static ArrayList<Integer> minus = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int number = Integer.parseInt(st.nextToken());
            if (number > 0) {
                plus.add(number);
            } else {
                minus.add(number);
            }
        }

        int n1 = 0, n2 = 0;
        int min = Integer.MAX_VALUE;
        if (minus.size() >= 2) {
            n1 = minus.get(minus.size() - 2);
            n2 = minus.get(minus.size() - 1);
            min = Math.abs(n1 + n2);
        }

        if (plus.size() >= 2 && (plus.get(0) + plus.get(1)) < min) {
            n1 = plus.get(0);
            n2 = plus.get(1);
            min = n1 + n2;
        }

        if (!plus.isEmpty()) {
            for (int i = 0; i < minus.size(); i++) {
                int index = lowerBound(Math.abs(minus.get(i)));
                if (index == plus.size()) {
                    int result = Math.abs(minus.get(i) + plus.get(index - 1));
                    if (result < min) {
                        min = result;
                        n1 = minus.get(i);
                        n2 = plus.get(index - 1);
                    }
                } else if (index == 0) {
                    int result = Math.abs(minus.get(i) + plus.get(index));
                    if (result < min) {
                        min = result;
                        n1 = minus.get(i);
                        n2 = plus.get(index);
                    }
                } else {
                    int result1 = Math.abs(minus.get(i) + plus.get(index));
                    int result2 = Math.abs(minus.get(i) + plus.get(index - 1));
                    int result = Math.min(result1, result2);
                    if (result < min) {
                        min = result;
                        n1 = minus.get(i);
                        n2 = (result == result1) ? plus.get(index) : plus.get(index - 1);
                    }
                }
            }
        }

        System.out.println(new StringBuilder().append(n1).append(' ').append(n2));
    }

    static int lowerBound(int n) {
        int max = plus.size();
        int min = 0;
        while (min < max) {
            int mid = (min + max) / 2;
            if (n > plus.get(mid)) {
                min = mid + 1;
            } else {
                max = mid;
            }
        }
        return min;
    }

}