[BOJ] 2470 : 두 용액(Java)

문제

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

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

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

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

입력

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

출력

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

---

💡 풀이

투 포인터를 사용하여 풀이해 보자. 

 

여기서 사용할 투 포인터는 각각 L, R로 L은 남아 있는 것들 중 제일 작은 원소를 가리키고, R은 남아 있는 것들 중 제일 큰 원소를 가리킬 것이다. 

 

문제에서 제공한 예시를 통해 확인해 보자.

-2	4	-99	-1	98
		L		R

맨 처음의 경우, L은 -99를 가리키고 R은 98을 가리키고 있을 것이다. 

이때, 이 둘을 더했을 때 다음과 같이 3개의 상황이 나타날 것이다. 

1. 최소 + 최대 < 0
2. 최소 + 최대 = 0
3. 최소 + 최대 > 0

1번의 경우부터 살펴보자. 

두 수, 최소와 최대를 더했는데 음수가 나왔다는 말은 최솟값(L, 현재는 -99) 입장에서 나머지 다른 숫자(용액)들을 더해볼 필요가 없다는 뜻이다. 가장 작은 숫자가 가장 큰 숫자를 더했는데도 음수가 나왔으면, 어떤 수를 더해도 음수가 나올 것이다. 

즉, 최소의 입장에서 최선책을 만난 상태이기 때문에 이를 더 고려할 필요가 없다(-99를 98과 함께 이용해서 얻을 수 있는 가장 좋은 숫자인 -1을 구했기 때문에). 그래서 이를 삭제한다. 그럼 남아 있는 원소 중 가장 작은 용액은 -2이기 때문에 L은 -2를 가리키게 된다.

-2	4	-99	-1	98
L		X		R

 

2번과 같은 경우는 정답을 찾은 것이기 때문에 바로 출력을 해주면 된다. 

 

3번의 경우에는 1번의 경우와 반대가 되는 상태이므로, R이 가리키는 숫자(용액)을 삭제해주면 된다. 

 

이것을 원소가 1개가 남았을 때까지 반복해주면 된다. 원소가 1개가 남으면 더이상 섞지 못하기 때문이다. 

오류

그럼 위의 방식대로 풀이를 진행하면 다음과 같다. 

1. 매 순간 L, R을 찾는다. 
2. 원소가 1개가 될 때까지 반복한다. 

1을 2가 될 때까지 반복하게 된다. 이때 시간 복잡도를 생각해보면, 1번의 경우 탐색이기 때문에 $O(N)$의 시간복잡도이고 이를 원소의 개수(N)만큼 반복해야하기 때문에 총 $O(N^2)$의 시간복잡도가 나오게 된다. 

해결책

이를 해결하기 위해 매번 탐색을 통해 L, R을 결정하지 말고 처음 배열을 입력 받았을 때, 정렬을 시키면 최소와 최대를 빠르게 알 수 있다. 정렬의 시간복잡도는 $O(NlogN)$이다. 다음과 같다.

1. 배열 정렬 시키기 → $O(NlogN)$
2. 매 순간 L, R로 계산한 후, 이동시키기 → $O(N)$
3. 총 시간 복잡도 → $O(NlogN)$

-99	-2	-1	4	98
L				R

위와 같이 시작되어 중간에서 L과 R이 같은 원소를 가리키게 되는 순간 종료하면 된다. 

 

전체적인 코드는 다음과 같다. 

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

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

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

        Arrays.sort(solutions); // 용액들을 정렬

        int best_sum = Integer.MAX_VALUE;
        int L = 0, R = N - 1;
        int v1 = 0, v2 = 0;

        while (L < R) { // L == R 인 상황이면 용액이 한 개 뿐이기 떄문에 종료
            int sum = solutions[L] + solutions[R];

            if (Math.abs(sum) < best_sum) { // 새롭게 계산한 sum이 기존의 best_sum보다 좋은 경우(0에 가까운 경우)
                best_sum = Math.abs(sum);
                v1 = solutions[L];
                v2 = solutions[R];
            }

            if (sum > 0) {
                R--;
            } else {
                L++;
            }
        }

        System.out.println(v1 + " " + v2);

    }

}