[99클럽 코테 스터디 5일차 TIL / 백준] 2470 - 두 용액 (JAVA)

99클럽 코테스터디 4일차 TIL
KeyWord : BinarySearch, Two Pointer

문제

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

 

---

풀이

이분 탐색, 두 포인터 탐색 두 가지 방법으로 해결할 수 있는 문제다.

두 가지 방법 모두 풀이해보았으며, 두 풀이 모두 입력은 BufferedReader를 활용했다. 마지막에는 시간 복잡도를 이용한 간단한 성능 비교를 진행했다.

 

이분 탐색

이분 탐색 문제만 5일 연속 풀고 있다보니 당연하게도 가장 먼저 떠오른 것은 이분 탐색이었다.

5
-2 4 -99 -1 98

먼저 주어진 입력을 배열에 담아 정렬한다.

-99 -2 -1 4 98

왼쪽 값의 인덱스부터 차례데로 이분 탐색의 매개변수로 넘기고, 이 값보다 큰 특성값을 가지는 용액들만을 이용해 이분 탐색을 진행하는 방식으로 진행했다.

int ans1=0, ans2=0;  
int min_density = Integer.MAX_VALUE;  
for (int i = 0; i < n-1; i++) {  
    int value = binarySearch(solution, i);  

    int current_density = Math.abs(solution[value] + solution[i]);  
    if(current_density < min_density) {  
        min_density = current_density;  
        ans1 = i;  
        ans2 = value;  
    }  
    if(current_density == 0) {  
        break;  
    }
}

1. -99를 가장 0에 가깝게 만드는 값을 찾는다.
2. -2를 가장 0에 가깝게 만드는 값을 찾는다. 이때, -2보다 작은 값은 이분 탐색에 포함할 필요 없다.
3. 1, 2 중 더 0에 가까운 조합을 저장한다.
4. 탐색 중, 농도가 정확히 0이 되었을 경우 탐색을 종료한다. 그렇지 않다면 계속 반복한다.

이제 이분 탐색 내부를 보자.

private static int binarySearch(int[] solution, int idx) {  
    int lo = idx+1;  
    int hi = solution.length;  
    int current_density;  
    int min_density = Integer.MAX_VALUE;  
    int min_density_idx = -1;  

    while (lo < hi) {  
        int mid = lo + (hi - lo) / 2;  
        current_density = solution[idx] + solution[mid];  

        if (Math.abs(current_density) < Math.abs(min_density)) {  
            min_density = current_density;  
            min_density_idx = mid;  
        }  

        if(current_density < 0) {  
            lo = mid+1;  
        } else if(current_density > 0) {  
            hi = mid;  
        } else {  
            return min_density_idx;  
        }  
    }  
    return min_density_idx;  
}  

여기서 우리가 찾아야 할 값은 solution[idx]와 혼합해 가장 농도를 0에 가깝게 만드는 용액이다.

solution[mid]와 solution[idx]를 섞었을 때의 농도를 current_density로 설정한 후, 이것을 key로 삼아 이분 탐색을 진행한다. 이때 중요한 것

이 값이 0보다 작다면 지금 값보다 더 큰 값을 더해야 한다.
이 값이 0보다 크다면 지금 값보다 더 작은 값을 더해야 한다.

여기서 의문이 들 수도 있다.

Q. 무조건 값을 더한다고 0에 가까워지는 건 아니지 않나요?

옳은 의문이다. 하지만, 간과하지 말아야할 것은 위 코드에서 min_density, 즉, 최저 농도를 저장하고 있다는 것이다.

이 이분 탐색은 정확히 말하자면, 두 용액을 합쳤을 때 0이 되는 mid 값을 찾는 것이다.

중요한 건 탐색에 실패했을 경우다. 평범한 이분탐색이라면 -1을 반환하고 탐색에 실패했음을 알린다. 하지만, 이 문제와 같은 경우에는 0이 되는 mid가 존재하지 않을 경우 가장 0에 가까웠던 용액의 위치를 반환하게끔 한다. 즉, 탐색에 실패했을 경우 min_density를 반환하면 된다.

코드

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());  

        int[] solution = new int[n];  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        for (int i = 0; i < n; i++) {  
            solution[i] = Integer.parseInt(st.nextToken());  
        }  
        Arrays.sort(solution);  

        int ans1=0, ans2=0;  
        int min_density = Integer.MAX_VALUE;  
        for (int i = 0; i < n-1; i++) {  
            int value = binarySearch(solution, i);  

            int current_density = Math.abs(solution[value] + solution[i]);  
            if(current_density < min_density) {  
                min_density = current_density;  
                ans1 = i;  
                ans2 = value;  
            }  
            if(current_density == 0) {  
                break;  
            }
        }

        System.out.println(solution[ans1] + " " + solution[ans2]);  
    }  

    private static int binarySearch(int[] solution, int idx) {  
        int lo = idx+1;  
        int hi = solution.length;  
        int current_density;  
        int min_density = Integer.MAX_VALUE;  
        int min_density_idx = -1;  

        while (lo < hi) {  
            int mid = lo + (hi - lo) / 2;  
            current_density = solution[idx] + solution[mid];  

            if (Math.abs(current_density) < Math.abs(min_density)) {  
                min_density = current_density;  
                min_density_idx = mid;  
            }  

            if(current_density < 0) {  
                lo = mid+1;  
            } else if(current_density > 0) {  
                hi = mid;  
            } else {  
                return min_density_idx;  
            }  
        }  
        return min_density_idx;  
    }  
}

 

두 포인터 탐색

이 방법은 조금 더 간단하다.

배열을 정렬한 후, 왼쪽과 오른쪽을 한 칸씩 줄여가면서 범위를 좁히는 방식이다.

-99 -2 -1 4 98

1. -99 -2 -1 4 98 → min_density=-1 current_density=-1: 0보다 작으므로 left를 한 칸 옮긴다.
2. -99 -2 -1 4 98 →  min_density=-1 current_density=97 : 0보다 크므로 right를 한 칸 옮긴다.
3. -99 -2 -1 4 98 → min_density=-1 current_density=2 : 0보다 크므로 right를 한 칸 옮긴다.
4. -99 -2 -1 4 98 → min_density=-1 current_density=-3 : 0보다 크므로 left를 한 칸 옮긴다.
5. -99 -2 -1 4 98 : left와 right가 같은 값을 가리키므로 탐색을 종료한다.
6. 가장 0에 가까운 농도를 만들었던 -99, 98이 정답이 된다.

이 방법을 그대로 코드로 구현하면 된다.

코드

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());  

        int[] solution = new int[n];  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        for (int i = 0; i < n; i++) {  
            solution[i] = Integer.parseInt(st.nextToken());  
        }  
        Arrays.sort(solution);  

        int[] ans = twoPointerSearch(solution);  
        System.out.println(solution[ans[0]] + " " + solution[ans[1]]);  
    }  

    private static int[] twoPointerSearch(int[] solution) {  
        int left = 0, right = solution.length-1;  
        int min_density = Integer.MAX_VALUE;  
        int[] ans = {left, right};  

        while (left < right) {  
            int current_density = solution[left] + solution[right];  
            if(Math.abs(current_density) < Math.abs(min_density)) {  
                min_density = current_density;  
                ans[0] = left;  
                ans[1] = right;  
            }  

            if(current_density < 0) {  
                left++;  
            } else if (current_density > 0) {  
                right--;  
            } else {  
                // 농도가 0이 되었을 경우 더 탐색할 필요 없으므로 바로 return
                return ans;  
            }  
        }  

        return ans;  
    }  
}

 

---

성능

• 이분 탐색 : $O(n log n)$
  • 외부 반복문 $n$ $\times$ 이분탐색 $log{n}$
• 투 포인터 탐색 : $O(n)$

정렬은 두 코드에 모두 해당되므로 포함하지 않았다.

하지만 최악의 경우를 계산하는 것이기에, 문제에 제출했을 경우 성능 차이는 보이지 않았다. 아마 농도가 0이 되었을 경우 조기 종료가 되게끔 가지치기 코드를 넣어놓은 것 때문에 그런 듯싶다.