<두 포인터> BOJ 2470 두 용액

문제

산성 용액과 알칼리성 용액의 특성값이 배열로 주어질때 두 용액의 특성 값의 합이 0에 가장 가까운 경우를 찾는 문제입니다.(절대값이 작으면 되겠죠?)

• 전체 용액의 수 N <= 100000

접근

• 1. 이중 for문을 사용했다간 100억이라는 숫자를 맞을 테니 이중 for문을 대체할 두 포인터 알고리즘을 떠올린다.
• 2. 두 포인터 알고리즘을 적용하고자 하니 음수가 걸린다.
• 3. 하지만 문제가 합이 가장 크거나 가장 작은걸 고르는게 아닌 0에 가까운 수를 고르는 것이다. 따라서 이런 전략을 생각해본다.
  • 3-1. 배열을 정렬한다.
  • 3-2. 포인터 두개를 각각 0과 배열 마지막에 둔다.
  • 3-3. 두개의 합이 0보다 작다면 왼쪽 포인터를 오른쪽으로 움직인다.
  • 3-4. 두개의 합이 0보다 크다면 오른쪽 포인터를 왼쪽으로 움직인다.
    3-3, 3-4 두 경우 모두 커지거나 작아질 것이 확실하므로 두 포인터를 사용 가능하다.
• 4. 반대 방향에서 포인터가 출발하므로 $O(N)$에 해결 가능합니다.

코드

import java.io.*;
import java.util.*;

class Pair {
    int i;
    int j;
    int val;

    Pair(int i, int j, int val) {
        this.i = i;
        this.j = j;
        this.val = val;
    }
}

class baek__2470 {

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

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        String[] temp = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(temp[i]);
        }

        Arrays.sort(arr);

        int p1 = 0;
        int p2 = arr.length - 1;
        Pair pair = new Pair(-1, -1, -1);

        int sum = arr[p1] + arr[p2];
        pair.i = p1;
        pair.j = p2;
        pair.val = sum;

        while (p1 < p2) {
            if (Math.abs(sum) < Math.abs(pair.val)) {
                pair.i = p1;
                pair.j = p2;
                pair.val = sum;
            }

            if (sum > 0) {
                sum -= arr[p2];
                p2--;
                sum += arr[p2];
            } else if (sum == 0) {
                break;
            } else {
                sum -= arr[p1];
                p1++;
                sum += arr[p1];
            }
        }

        System.out.print(arr[pair.i] + " " + arr[pair.j]);
    }
}