[백준/JAVA] BOJ 2470 - 두 용액

저엉말 오랜만에 적어보는 알고리즘 풀이! 꾸준히 알고리즘은 풀고 있었는데, 블로그에 안 적다 보니 약 1년이 지나버렸네요... 오늘부터 다시 열심히 벨로그에 기록해 보겠습니다! 🥺

👀 문제

2470번: 두 용액 ✨ 골드 5

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

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

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

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

예제 입력

5
-2 4 -99 -1 98

예제 출력

-99 98

🔑 키포인트

이분 탐색 투 포인터

✍️ 코드

1️⃣ 오름차순 정렬해 주기

2️⃣ 양 끝에 포인터 두고 시작 (start < end 동안 수행)

3️⃣ 두 수의 합이 양수인 경우 end--, 음수인 경우 start++
🤷 0에 가깝게 만들어야 하기 때문에 합이 양수인 경우 수의 크기를 줄이려면 더 작은 수가 필요하고, 합이 음수인 경우 더 큰 수가 필요하기 때문

4️⃣ 이때 만약에 합이 0이라면 그냥 바로 출력 (경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력하라고 했으므로)

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

public class BOJ2470_두용액 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];

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

        int start = 0;
        int end = n - 1;
        int answer = Integer.MAX_VALUE;
        int[] ans = new int[2];

        Arrays.sort(arr); // 오름차순 정렬

        while (start < end) {
            int hab = arr[start] + arr[end];
            if (answer > Math.abs(hab)) {
                answer = Math.abs(hab);
                ans[0] = arr[start];
                ans[1] = arr[end];
            }
            if (hab > 0) {
                end--;
            } else if (hab < 0) {
                start++;
            } else {
                System.out.println(arr[start] + " " + arr[end]);
                break;
            }
        }
        System.out.println(ans[0] + " " + ans[1]);
    }
}