[백준] 2470번 - 두 용액 (Gold 5)

문제 링크

백준 2470번 - 두 용액 (Gold 5)

문제 설명

수열이 주어져있을 때, 두 수의 합이 0에 가장 가깝도록 하는 수 두개를 출력하면 된다.
만약 방법이 여러가지라면, 그 중 한 가지를 아무거나 출력해도 된다.

정답 코드 및 설명

먼저 수열을 정렬하고, 순차적으로 탐색을 진행하였다.
첫 수를 정해두고, 이분탐색을 통해 첫 수와의 합이 가장 0에 가까운 두번째 수를 찾았다.
이렇게 얻어진 두 수의 합을 전부 비교하여 가장 작은 조합을 골랐다.
이 방식의 시간 복잡도는 $O(N\log N)$이다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ2470 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] value = new int[n];
        for (int i = 0; i < n; i++)
            value[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(value);
        int[] neutral = neutral(value, n);
        bw.write(neutral[0] + " " + neutral[1]);
        bw.close();
    }

    static int[] neutral(int[] value, int n) {
        int first = 0, second = 1;
        // 초기 두 용액의 특성값의 합의 절댓값
        int valueSum = value[0] + value[1];
        if (valueSum < 0)
            valueSum = -valueSum;
        // i와 이후 용액의 특성값의 합의 절댓값이 최소가 되도록 한다
        for (int i = 0; i < n - 1; i++) {
            // 이분탐색
            int j = i + 1;
            int end = n;
            while (j + 1 < end) {
                int mid = (j + end) / 2;
                // 정확히 0이 되면 리턴
                if (value[i] + value[mid] == 0)
                    return new int[] { value[i], value[mid] };
                // 0보다 작은 최대의 원소 찾기
                if (value[i] + value[mid] > 0)
                    end = mid;
                if (value[i] + value[mid] < 0)
                    j = mid;
            }
            int vCan = value[i] + value[j];
            if (vCan < 0)
                vCan = -vCan;
            if (j != n - 1 && value[i] + value[j + 1] < vCan) {
                vCan = value[i] + value[j + 1];
                j = j + 1;
            }
            if (vCan < valueSum) {
                first = i;
                second = j;
                valueSum = vCan;
            }
        }
        return new int[] { value[first], value[second] };
    }
}