n = int(input())
_list = sorted(list(map(int, input().split()))) # 이분 탐색을 위해 정렬
l, r = 0, n - 1
_min = abs(_list[l] + _list[r]) # 0에 가까운 수
answer = [_list[l], _list[r]] # 정답 배열
while l < r:
_sum = _list[l] + _list[r] # 두 용액의 합
if abs(_sum) < _min: # 0에 더 가깝다면
_min = abs(_sum) # 갱신
answer = [_list[l], _list[r]] # 갱신
if _min == 0: # 합이 0이면, 더 이상 비교하지 않아도 된다.
break
if _sum >= 0: # 합이 양수 or 0 이라면
r -= 1
else: # 합이 음수라면
l += 1
print(*answer)
투 포인터 + 이분 탐색 문제이다.
처음에 음수, 양수 용액을 나눠서 저장하고 음수 포인터, 양수 포인터를 생각했었는데, 이렇게 되면 문제의 음수 + 음수 or 양수 + 양수로도 답이 될 수 있다는 조건에 위배된다.
(음수, 양수의 합만 구하게 되고 만약 음수만 있다면 합을 구할 수 없기 때문)
문제를 보면, 용액의 순서는 변경되어도 상관없다.
따라서, 이분 탐색을 사용하기 위해 먼저 정렬해준 뒤 일반적인 이분탐색을 수행한다.
단, 이때 mid를 설정하는게 아닌 두 포인터가 가르키는 용액의 합이 0에 가까운지를 비교하여 답을 갱신하고,
합이 0 또는 양수라면 r을 줄이고, 음수라면 l을 늘린다. → WHY? 최대한 합이 0에 가까운 두 용액을 찾아야 하므로
음수 용액만 입력될 수 있고 양수 용액만 입력될 수 있는 경우에는 l과 r이 음수 포인터, 양수 포인터가 된다.
그렇지 않은 경우에는 l과 r이 최솟값 포인터, 최댓값 포인터가 된다.