문제

풀이 과정

요약

투 포인터를 활용한 용액 문제.

상세

1. 입력값이 오름차순으로 주어진다에 주목하자.
2. 현재 입력값의 최대 최소를 기점으로 하여, 0 에 가까운 용액의 합을 찾는다. $l, r$
3. $r$ 을 예로 들어보자. 현재 두 용액의 합이 $x$ 라면, $r$ 이 작아질 수록 $x$ 역시 점점 작아지게 된다. 본 문제는 0 에 가까운 값을 찾는 것이므로, $x$ 가 0보다 큰 경우라면 지속적으로 $r$ 을 줄인다.
4. $l$ 을 예로 들어보자. 현재 두 용액의 합이 $x$ 라면, $l$ 이 커질 수록 $x$ 는 점점 커지게 된다. 본 문제는 0 에 가까운 값을 찾는 것이므로, $x$ 가 0보다 작은 경우라면 지속적을 $l$을 키운다.
5. 3~4의 과정을 매 상황마다 반복하면 0 혹은 현재 배열에서 0에 가장 가까운 용액의 합을 찾을 수 있다.

정답

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

public class Main {
    static int[] arr;
    static int N;
    static int ans = 987654321;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        StringTokenizer stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(stk.nextToken());
        int l = 0;
        int r = arr.length - 1;

        while (l < r) {
            int val = arr[l] + arr[r];
            if(Math.abs(ans) > Math.abs(val)) ans = val;
            if (val == 0) break;
            else if (val > 0) r--;
            else l++;
        }

        System.out.println(ans);
    }
}