BOJ 2473 세 용액

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

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-2, 6, -97, -6, 98]인 경우에는 특성값이 -97와 -2인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 세 종류의 알칼리성 용액만으로나 혹은 세 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액이 주어졌을 때, 이 중 같은 양의 세 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액을 찾는 프로그램을 작성하시오.

---

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

---

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액의 특성값을 출력한다. 출력해야하는 세 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

---

예제 입력 1

5
-2 6 -97 -6 98

예제 출력 1

-97 -2 98

예제 입력 2

7
-2 -3 -24 -6 98 100 61

예제 출력 2

-6 -3 -2

---

코드

어디서 본 문제 같던데, 알고보니 이전에 풀었던 BOJ 2467 용액에서 한 가지 용액을 더 섞는 조건이 추가된 문제였다.

이전 용액 문제에서는 두 용액을 투 포인터 방식으로 더해서 0보다 크다면 rightIndex를 줄이고, 0보다 작으면 leftIndex를 늘리는 방식으로 구현했다.

이번 문제를 처음 풀었을 때는 위 방식과 비슷하지만, 용액을 섞을 때 한 용액은 이미 두 개의 용액을 섞은 용액으로 해서 브루트포스 방식으로 탐색했지만, 역시 실패했다.

이후 잘 생각해보니, 굳이 그럴 필요 없이 한 용액을 뽑아놓고, 나머지 두 용액을 이전 방식처럼 뽑아서 검사하면 되는 것이였다.

이전 문제 풀이의 시간 복잡도가 O(n)이었고, 위 방식과 같이 풀면 O(n^2)이기 때문에 용액 수가 5,000인 이 문제는 충분히 풀 수 있었다.

다만, 이전 문제와 달라 주의할 점은 다음과 같다.

1. 입력으로 주어지는 용액이 오름차순 정렬되어 있지 않은 것
2. 세 용액을 합치는 것이므로 long 타입의 변수를 사용해야 할 것

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

public class Main {

    static long minSum = Long.MAX_VALUE;
    static int[] liquids;
    static long[] picked = new long[3];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        liquids = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            liquids[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(liquids);

        for (int i = 0; i < N - 2; i++) {
            if(search(i)) {
                break;
            }
        }

        Arrays.sort(picked);
        StringBuilder answer = new StringBuilder();
        for (long liquid: picked) {
            answer.append(liquid).append(' ');
        }

        System.out.println(answer);
    }

    static boolean search(int index) {
        int lIdx = index + 1;
        int rIdx = liquids.length - 1;

        while (lIdx < rIdx) {
            long sum = (long)liquids[lIdx] + liquids[rIdx] + liquids[index];
            long absSum = Math.abs(sum);

            // 현재 검사 중인 세 용액의 혼합물이 이전 조합들보다 0에 더 가까운 경우
            if(minSum > absSum) {
                picked[0] = liquids[lIdx];
                picked[1] = liquids[rIdx];
                picked[2] = liquids[index];
                minSum = absSum;

                // 혼합물의 특성값이 0이면, 더 탐색할 필요 없다는 의미로 true 반환
                if(absSum == 0) {
                    return true;
                }
            }

            if(sum > 0) {
                rIdx--;
            } else {
                lIdx++;
            }
        }

        return false;
    }
}