[백준] 두 용액 Java

두 용액

투 포인터 문제입니다.

투 포인터의 장점은 어떤 상황이라도 O(n)에 끝내는 시간 복잡도로,
배열이 연속적인 특징을 가지고 있어야 합니다.

정답을 구하려면 0에 가까운 알칼리성 산성 용액을 골라야 합니다.

일단 연속성을 만들어주기위해 sort를 한 후
left/right 인덱스를 양 끝으로 잡아주고 하나씩 비교하며 인덱스를 움직입니다.

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));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

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

        int target = 0;
        int right = N-1;
        int left = 0;
        int sum = 0;
        int rslt = Integer.MAX_VALUE;
        int[] rsl = new int[2];

        while (left < right) {
            sum = arr[right] + arr[left];
            int tmp = Math.abs(sum);
            if (tmp < rslt) {
                rslt = tmp;
                rsl[0] = arr[left];
                rsl[1] = arr[right];
            }

            if (sum > target) right--;
            else left++;
        }

        System.out.println(rsl[0] + " " + rsl[1]);

    }
}