[TIL-25/01/21] 99클럽 코테 스터디 5일차 - 백준 2470: 두 용액 - JAVA

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

문제

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에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

 

문제 접근

이 문제의 제한 시간은 `1초`이고 주어진 입력의 크기는 약 `100000`개이다. 이런 경우 브루트 포스(모든 경우를 탐색하는 방법)은 비효율적일 가능성이 높다. 

 

시간 복잡도가 O(N log N) 정도의 효율성을 가진 알고리즘으로 접근하는 것이 좋다.

 

여기서 생각한게 이분탐색이다. 해당 문제를 살펴보면 두 용액에 합의 절대값을 기준하여 최소값을 만족해야 하므로 정렬된 배열구조가 도움이 될 수 있음을 알 수 있다.

 

이런 정렬된 구조를 만들었을때, 선택된 두 타겟에 대한 기준을 만들 수 있게 된다. 

• 합이 0보다 크면, 더 작은 합을 만들기 위해 오른쪽 값으로 왼쪽으로 이동해야 한다. (정렬됨에 따라 오른쪽은 큰 값이 위치하니깐)
• 합이 0보다 작으면, 더 큰 합을 만들기 위해 왼쪽 값을 오른쪽으로 이동해야 한다.

 

이런 구조를 생각해보면 동작방식이 이분탐색과 비슷하다는 것을 알 수 있다. 이것을 기반으로 이제 코드를 작성해보자. 

 

코드

package backjoon.gold.lv5;

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

public class B2470 {

    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[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int start = 0;
        int end = arr.length - 1;
        int target = Integer.MAX_VALUE;

        int result1 = 0;
        int result2 = 0;

        while (start < end) {
            int sum = arr[start] + arr[end];

            if (Math.abs(sum) < Math.abs(target)) {
                target = sum;
                // 이 순간이 조건에 맞는 경우이다.
                result1 = arr[start];
                result2 = arr[end];
            }

            if(sum < 0) {
                start++; //음수 값이 크니까 왼쪽 포인터를 옮겨준다
            }
            else {
                end--; //양수 값이 크니까 오른쪽 포인터를 옮겨준다.
            }
        }

        System.out.println(result1 + " " + result2);
    }
}

 

이분 탐색을 위한 기본 세팅

Arrays.sort(arr);

int start = 0;
int end = arr.length - 1;
int target = Integer.MAX_VALUE;

int result1 = 0;
int result2 = 0;

while (start < end) {


}

이분 탐색을 하기 위해선 시작값(`start`)와 종료값(`end`)를 다루는 변수가 필요하다. 그런 다음 조건을 처리할 `target`이 필요하다. 이 값은 두 용액의 합과 비교 값으로 쓰이기 때문에 `MAX_VALUE`로 기본 세팅을 한다.

 

그리고 출력 값에 활용된 `result1`과 `result2`을 미리 선언해두도록 한다. 해당 변수에 설명은 아래에 나올 예정이다.

 

마지막으로 이분 탐색에 기본 조건인 시작 값이 종료 값보다 커지게 되면 루프를 종료한다. 조건과 함께 루프문을 실행한다. 

 

이분 탐색 내부 코드

while (start < end) {
    int sum = arr[start] + arr[end];

    if (Math.abs(sum) < Math.abs(target)) {
        target = sum;
        // 이 순간이 조건에 맞는 경우이다.
        result1 = arr[start];
        result2 = arr[end];
    }

    if(sum < 0) {
        start++; //음수 값이 크니까 왼쪽 포인터를 옮겨준다
    }
    else {
        end--; //양수 값이 크니까 오른쪽 포인터를 옮겨준다.
    }
}

문제에서 두 용액의 합이 특성 값을 나타내므로 합산을 위한 변수(`sum`)와 두 값을 더해 초기화를 해준다. 

 

그럼 다음, 합산 값이 `0`에 가까운 수인지 판별을 해야한다. 기본적으로 특정 수에 가까운 지 여부를 확인하는 것은 `특정값 - |합산의 수|`형태로 표기되지만, 해당 문제에선 `0`에 가장 가까운 수를 찾는 것이므로 가장 작은 절대 값을 구하면 된다. `target`에 경우 가장 작은 값으로 표현된 `sum`값을 최신화 하는 값으로 이 조건에 해당하면 다음과 같은 동작을 하게 된다. 

• `target`을 `sum`값으로 갱신한다. 
• `result1`와 `result2`을 현재 입력 배열의 값으로 갱신한다. 

 

조건을 보면 알겠지만, 갱신되는 `target`의 절대값을 현재 가장 0에 가까운 수가 갱신이 된다. 그러므로 이분 탐색이 종료되었을때, `result1`과 `result2`에 들어있는 값은 값을 만들기 위한 최소값이 들어가 있는것을 알 수 있다. 

 

마지막으로 정렬된 배열안에서 `sum`의 값이 양수인 경우 오른쪽 포인트를 감소시켜 0에 가까운 수로 만들고, 음수인 경우 왼쪽 포인트를 증가시켜 0에 가까운 수로 만드는 법칙으로 진행된다. 

 

경우에 따라 아래 코드처럼 탈출 코드를 만들어도 되지만, 해당 문제에선 넣든 말든 모두 통과가 된다.

while (start < end) {
    int sum = arr[start] + arr[end];

    // 탈출 조건
    if(sum == 0) {
        System.out.println(arr[start] + " " + arr[end]);
        return;
    }

    if (Math.abs(sum) < Math.abs(target)) {
        target = sum;
        // 이 순간이 조건에 맞는 경우이다.
        result1 = arr[start];
        result2 = arr[end];
    }

    if(sum < 0) {
        start++; //음수 값이 크니까 왼쪽 포인터를 옮겨준다
    }
    else {
        end--; //양수 값이 크니까 오른쪽 포인터를 옮겨준다.
    }
}

 

정리(이분탐색과 투포인터)

사실 이분 탐색이란 표현을 사용했지만, 내가 푼 방식은 투 포인터에 가깝다. 왜냐하면 이분으로 나눠 탐색하는 과정이 없기 때문이다. 

 

제대로 된 이분 탐색으로 풀기 위해선 다음 코드 진행으로 풀면 된다.

Arrays.sort(arr);

int closestSum = Integer.MAX_VALUE;
int result1 = 0, result2 = 0;

for (int i = 0; i < N - 1; i++) {
    int fixed = arr[i]; // 첫 번째 값을 고정
    int target = -fixed; // 두 번째 값의 목표(0에 가장 가까운 합을 위해)
    int low = i + 1, high = N - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int sum = fixed + arr[mid];

        if (Math.abs(sum) < Math.abs(closestSum)) {
            closestSum = sum;
            result1 = fixed;
            result2 = arr[mid];
        }

        if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
}

System.out.println(result1 + " " + result2);

1. 주어진 크기인 `N-1`만큼 루프를 돌며, 첫 번째 값을 고정한다. (`int fixed`) 
   • 정렬된 배열을 사용하기 때문에 마지막 값은 다음 값이 없기 때문에 루프를 돌 필요가 없다.
2. target은 `-fixed`값인데, `fixed + other ≈ 0`식이 기본 구조이므로 이 식을 변경하면 `other ≈ −fixed`이며, 따라서 고정된 값에 대하 두 번째 용액(`other`)가 `-fixed`에 가까운 값이 되어야 한다. 
3. 이 후 코드를 위에서 설명한 방식과 동일하게 동작하게 된다.

 

이분탐색을 코드를 보면 고정된 값을 깔고 그 루프안에 이분탐색 로직이 존재하는게 그렇게 하는 방식을 찾아보니, 한 값을 고정하지 않으면 이분 탐색을 적용할 기준을 설정하기 어렵다고 한다. 만약 고정 값을 설정하지 않는다면 두 값을 동시에 탐색해야하니, 이 경우 `N × N = O(N^2)`방식이 될 수 있다.