[백준/투 포인터] - 두 용액

문제 링크

코드

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이 최솟값 포인터, 최댓값 포인터가 된다.