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

[jusung-c]

문제 링크

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

문제 조건

-1,000,000,000 부터 1,000,000,000까지의 특성을 가진 N개의 용액이 주어졌을 때 두 용액을 더해 0에 가장 가까운 혼합 용액을 만드는 경우를 구하시오

• N은 2 이상 100,000 이하

---

아이디어

두 용액을 완전탐색으로 뽑아서 더해보기에는 N의 범위가 너무 커서 시간 안에 풀 수 없다.

용액을 하나 골랐다고 가정하자. 고른 용액이 A[i]라면 A[i]와 더해서 0에 가장 가까우려면 -A[i]와 가장 가까워야 한다.

정렬의 특성 중 “각 원소마다 가장 가까운 원소는 자신의 양 옆 중에 있다.”가 있었다. 정렬을 이용해 -A[i]와 가장 가까운 용액을 찾아보자

for문으로 용액을 하나씩 고른 후 나머지 용액을 고를 것이다.
어짜피 for 문으로 모든 용액을 비교할 것이므로 탐색범위는 기준 용액의 오른쪽 용액들인 A[i + 1] ~ A[N] 만 탐색해줘도 빠지는 케이스 없이 비교 가능하다.

1. 용액 리스트를 정렬 - O(N logN)

2. 모든 원소마다 이분 탐색으로 가장 가까운 원소 찾기 - O(N logN)

   • 처음 기준이 되는 용액이 list[i]라면 -list[i]와 가장 가까운 용액을 [i+1 ~ N) 영역에서 찾아야 한다.
   • -list[i] 이상의 수 중 가장 작은 수의 index를 구한다. 그렇다면 찾아야 하는 원소 후보는 list[index], list[index-1]이 된다.
   • 후보 둘 다 혼합해본 뒤 0과 가장 가까운 용액을 찾아낸다.

---

구현

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br;
    static StringTokenizer st;
    static int N;
    static int[] list;

    public static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        list = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
    }

    private static void pro() throws IOException {
        Arrays.sort(list);

        int A = 0;
        int B = 0;
        int sum = Integer.MAX_VALUE;

        for (int i = 0; i < list.length; i++) {
            int target = list[i] * -1;

            // 오른쪽 구간에서 가장 가까운 용액 찾기
            int up_index = upSearch(i + 1, list.length - 1, target);

            // up_index 범위 체크
            if (i + 1 <= up_index && up_index < N) {
                // 최솟값일 경우에만 갱신
                int result = Math.abs(list[i] + list[up_index]);
                if (sum > result) {
                    sum = result;

                    A = list[i];
                    B = list[up_index];
                }
            }

            // up_index - 1 범위 체크
            int down_index = up_index - 1;
            if (i + 1 <= down_index && down_index < N) {
                // 최솟값일 경우에만 갱신
                int result = Math.abs(list[i] + list[down_index]);
                if (sum > result) {
                    sum = result;

                    A = list[i];
                    B = list[down_index];
                }
            }
        }

        bw.write(A + " " + B + " ");

    }

    private static int upSearch(int start, int end, int target) {
        int result = end + 1;

        // target 이상인 수 중 가장 작은 수
        while (start <= end) {
            int mid = (start + end) / 2;

            if (list[mid] == target) {
                end = mid - 1;
                result = mid;
            } else if (list[mid] < target) {
                start = mid + 1;
            } else if (list[mid] > target) {
                end = mid - 1;
                result = mid;
            }
        }

        return result;

    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}