[백준/Java] 2470 두 용액

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

1. 문제 요약

여러 산성 용액과 알칼리성 용액이 있다.
각 용액의 특성은 정수로 나타낼 수 있다.
산성은 1부터 10억까지의 양의 정수로, 알칼리성은 -1부터 -10억까지의 음의 정수로 나타난다.
두 용액을 혼합한 용액의 특성은 두 용액의 특성 합으로 얻어진다.
두 용액을 혼합하여 특성이 0에 가장 가까운 경우를 얻는 두 용액을 찾아라.
참고로, 알칼리성 용액 또는 산성 용액만으로 정답을 얻는 경우도 있을 수 있다.

전체 용액의 개수 N은 최대 10만
용액의 특성값은 최소 -10억, 최대 10억
N개 용액의 특성값은 모두 서로 다르고, 산성이나 알칼리성 용액만 주어질 수도 있다.

2. 문제 접근

일단 두 특성값의 합이 최소 -20억, 최대 20억이므로 int형을 사용해도 괜찮다.
전체 용액의 개수가 최대 10만이기 때문에 시간복잡도는 $O(NlogN)$까지 가능하다.
만약 완전탐색으로 모든 경우의 수를 확인한다면 $O(N^2)$이므로 시간복잡도가 넘친다.

이 문제를 해결하기 위해서는 투포인터를 사용해야 한다.
일단 모든 용액의 특성값을 받아 이를 오름차순으로 정렬한다.
그리고 투포인터를 설정해야 하는데, 보통 투포인터는 같은 한쪽 끝에서 시작해서 속도를 다르게 하는 방법, 또는 양 쪽 끝에서 시작해 만나게 하는 방법이 있다.
여기서는 두 용액의 합이 0이 가까운 경우를 찾는 것이므로 양 쪽 끝에 각각 포인터를 설정하는 방식으로 해결할 수 있다.

3. 풀이

기본적인 아이디어는 다음과 같다.

1. 입력받은 용액의 특성값을 정렬한다.
2. 양 쪽 끝에 left, right라는 포인터를 생성하여 두 포인터가 만날 때까지 루프를 돌린다.
   2.1. 두 포인터가 가리키는 용액의 합을 구해 기존의 최선 값과 비교하여, 절대값이 더 작다면 값을 갱신한다.
   2.1. 두 용액의 합이 양수면 right를 왼쪽으로 한 칸 이동한다.
   2.2. 두 용액의 합이 음수면 left를 오른쪽으로 한 칸 이동한다.
   2.3. 두 용액의 합이 0이라면 이것보다 더 나은 정답은 없으므로 루프를 끝낸다.

유의할 점은 합을 구하는 것이 아니라 그 때의 두 용액 특성값을 구하는 것이기 때문에 그 값을 따로 기록해야 한다.
출력할 때는 left, right가 가리키는 특성값을 순서대로 출력하면 된다.
이러한 방식을 수행하면 정렬이 가장 큰 시간복잡도를 가지므로 전체 시간복잡도는 $O(NlogN)$이 될 것이다.

이를 구현한 코드는 다음과 같다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력 받기
        int N = Integer.parseInt(br.readLine());

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

        // 입력 특성값 정렬
        Arrays.sort(attribute);

        // 투포인터에서 사용할 포인터
        int left = 0;
        int right = N-1;

        // 최선의 값과 그 때의 두 포인터 기록
        int bestLeft = left;
        int bestRight = right;
        int bestSum = attribute[bestLeft] + attribute[bestRight];

        // 반복문으로 최선의 값을 찾아나간다.
        while (left < right) {
            int nowSum = attribute[left] + attribute[right];

            // 만약 지금의 합이 최선의 값보다 절대값이 더 작다면 갱신한다.
            if (Math.abs(nowSum) < Math.abs(bestSum)) {
                bestLeft = left;
                bestRight = right;
                bestSum = nowSum;
            }

            // 현재의 합이 양수면 right를 왼쪽으로 이동
            if (nowSum > 0) right--;
            // 현재의 합이 음수면 left를 오른쪽으로 이동
            else if (nowSum < 0) left++;
            // 현재의 합이 0이면 정답이므로 그냥 루프를 끝낸다.
            else break;
        }

        // 정답 출력
        System.out.println(attribute[bestLeft]+" "+attribute[bestRight]);
    }
}

4. 회고

투포인터를 설정할 때, 같은 쪽에서 시작해야 할 지, 양 쪽 끝에서 시작해야 할 지를 상당히 고민했다.
다만 이 문제에서 투포인터가 이동해야 하는 상황을 고려해보면, 같은 쪽에서 시작했을 때 두 포인터의 속도를 다르게 할 방법이 딱히 없기 때문에 양 쪽 끝에서 시작해야 한다는 점을 알 수 있다.