[백준] 2467: 용액 JAVA

접근

두 개의 용액을 섞어서 0에 가장 가까운 값을 만들고자 한다면, 결국 음수와 양수의 절댓값이 가장 비슷한 두 수를 더해야 한다. 이를 위해서 입력값을 저장하고 오름차순으로 정렬한 뒤, 가장 작은 수(배열의 왼쪽)와 가장 큰 수(배열의 오른쪽)를 가리키는 포인터 두 개를 통해 그 합을 비교한다.

 

left와 right는 배열의 각 끝을 가리키며, ansLeft와 ansRight는 두 용액의 합이 0에 가장 가까운 두 수를 가리킨다. minVal은 그 합의 절댓값에 해당한다. 용액의 특성값은 -1,000,000,000 ~ 1,000,000,000 사이에 해당하므로, 최악의 경우에는 그 합이 1,000,000,000 * 2가 될 수도 있다. 따라서 이를 MAX_VAL이라고 미리 선언해두어 minVal값을 초기화했다. 

 

두 포인터가 어긋나지 않을 때까지, 즉 left가 right보다 작을 때까지 반복하며 두 용액을 합해본다. 이때 합한 특성값이 양수라면 정렬된 배열에서 더 큰 수를 가리키고 있는 right를 줄이고, 음수라면 작은 수를 가리키고 있는 left를 올린다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int MAX_VAL = 1000000000 * 2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력값 저장 후 정렬
        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer> arr = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++)
            arr.add(Integer.parseInt(st.nextToken()));
        Collections.sort(arr);

        // 투 포인터 적용
        int left = 0, right = n - 1;
        int ansLeft = left, ansRight = right;
        int minVal = MAX_VAL; // 가장 최악의 경우

        while(left < right){
            int val = arr.get(left) + arr.get(right);

            if(Math.abs(val) <= minVal){
                minVal = Math.abs(val);
                ansLeft = left;
                ansRight = right;
            }

            if(val == 0) break;
            else if(val > 0) right--;
            else left++;
        }

        System.out.println(arr.get(ansLeft) + " " + arr.get(ansRight));
    }
}