BOJ 2467 용액

용액들의 개수 N이 첫 번째 줄에 주어지고 용액들의 특성값이 두 번째 줄에 오름차순으로 주어진다.

N은 2 ~ 100,000 이고
특성값은 -1,000,000,000 ~ 1,000,000,000 이다.

이 때 두 용액의 특성 값의 합이 0에 가장 가까운 한 쌍을 구해 출력하라

간단하게 모든 경우의 수 다 탐색하면 $O(10^{10})$으로 시간 초과가 된다.

투 포인터로 간단하게 양 쪽에서부터 접근해 해결할 수 있다.

예제인
[-99, -2, -1, 4, 98]의 경우

첫 번째 포인터는 맨 앞인 -99를 가리키고 두 번째 포인터는 맨 뒤인 98를 가리킨다.
두 포인터가 가리키는 값의 합인 1과 두 값을 저장하고
1. 합이 양수이면 두 번째 포인터를 한 칸 앞으로 당긴다.
2. 합이 음수라면 첫 번째 포인터를 한 칸 뒤로 민다.
3. 합이 0이라면 그 경우가 최적이다.

이 방식을 두 포인터가 엇갈리기 전까지 반복함으로써 해결할 수 있다.
시간복잡도: $O(N)$