BOJ 2467

문제

같은 양의 두 용액을 혼합하여 특성값이 0 에 가장 가까운 용액을 만들려고 한다.

입력

2 <= N <= 100,000

예제 입력 1
5
-99 -2 -1 4 98

예제 입력 2
4
-100 -2 -1 103

출력

예제 출력 1
-99 98

예제 출력 2
-2 -1

풀이

제한시간이 1초이고, 입력 범위가 $10^5$ 이므로 $n^2$ 의 시간복잡도를 넘어가면 안될 듯 하다. naive한 방식은 $n^2$ 인데 결국은 dp나 메모이제이션 등의 다른 풀이, 아이디어가 필요해 보인다.
그러다 투 포인터 방법으로 푸는게 직감적으로 맞겠다 싶었다.
문제는 투 포인터를 양끝에서 두고 시작하는것만 생각했는데, 검색 찬스로 시작부분에 l, r 두 포인터를 두고 푼다는 힌트를 듣고 풀었다.

투포인터 방식은 두 포인터를 어떻게 움직이는 기준을 세우는지가 관건인것 같다. +) 용액이 정렬을 안해도 된다.