코드포스 Contest 풀이 적다가 너무 힘들어서 잠깐 내려두고
쉴 겸, 백준에서 좀 쉬우면서 괜찮은 문제 찾다가 풀게 된 문제 '용액'을 풀이해보겠다.
(아 얼른 집가고 싶다)

BOJ 2467 - 용액 링크
(2022.09.01 기준 G5)
(치팅은 사회악...까지는 아니고 코딩악이야!)

문제

합이 0에 제일 가까운 두 원소 구하기

알고리즘

문제 조건을 보면 원소의 범위가 클 뿐, 원소의 개수의 최대는 100,000으로 충분히 작기 때문에 이런 문제는 바로 두 포인터로 풀면 된다고 생각이 들었다.

풀이

간단한 두 포인터 문제로 보인다. 두 포인터를 공부해봤다면 알겠지만 합이 최소나 최대 아니면 어떤 한 정수가 되게 하는 두 원소를 구하는게 두 포인터의 기본 문제이기 때문. 하지만 이 문제는 살짝 다르다. 두 원소의 합이 0에 제일 가까워야 하기 때문.

잘 생각해보자. 기본적인 두 포인터는 left = 0 right = 1 이렇게 시작을 할 것이다. 그러면서 조건에 따라 left나 right를 늘리면서 찾아가는게 두 포인터다.
하지만 이 문제에서 그렇게 하면, 합이 0에 가까워야 하기 때문에 left를 늘려야할지 right를 늘려야할지 애매하다.

여기서 발상을 떠올려야 한다. 이분 탐색처럼 범위를 좁혀나가야 한다는 것을.

먼저 합의 절댓값을 줄여나가야 하기 때문에 합의 절댓값 S의 초기값을 무한대로 설정해두자.
그리고 left는 0, right는 N - 1로 설정하고 탐색을 시작하자.

left번째와 right번째의 합을 s라 하면, s의 절댓값이 S보다 작다면
출력값을 left번째와 right번째로 갱신해주고 S에 s의 절댓값을 대입하자.

그 다음은, s가 0보다 작으면 i += 1 아니면 j -= 1을 해서 범위를 좁혀나가자.
이유는 다음과 같다. s가 0보다 작으면 더 큰 수를 더해줘야 하고, 아니면 더 작은 수를 더해줘야 한다. 그리고 원소는 오름차순으로 정렬되어 있기 때문에, 더 큰 수를 더해주기 위해선 left를 땡겨줘야 하고, 더 작은수를 더해주기 위해선 right를 땡겨줘야 한다.

그리고 탐색하다가 i와 j가 같아질 것이다. 그러면 탐색을 종료하고 출력값을 출력해주면 된다.

주의사항

S를 갱신할 때, 꼭 s의 절댓값으로 갱신하자.
당연한 소리지만 난 이걸 간과해서 맞왜틀 시전했음...

코드

import sys; input = sys.stdin.readline
from math import inf

N = int(input())
arr = list(map(int, input().split()))

# 합의 절댓값의 최소값 S는 무한대로 설정
S = inf
left = 0; right = N - 1

# 탐색 시작
while True:
    s = arr[left] + arr[right]
    if abs(s) < S: # 두 용액의 합 s의 절댓값이 S보다 작으면
        S = abs(s) # S룰 s의 절댓값으로 갱신
        answer = [arr[left], arr[right]] # 출력해줄 두 용액도 같이 갱신

    # 합이 0이면 더 이상 탐색 진행할 필요가 없음
    if not s:
        print(*answer)
        break

    if s < 0: # 합이 0보다 작으면 더 큰 수를 더해줘야 하므로
        left += 1 # left를 땡김
    else: # 합이 0보다 크면 더 작은 수를 더해줘야 하므로
        right -= 1 # right를 땡김

    #left와 right가 같아지면 탐색 종료 및 출력
    if left == right:
        print(*answer)
        break

여담

두 포인터에 대한 문제는 많이 접해보지 못했다. 그래서 사실 이 문제 좀 헤맸다.
앞으로 두 포인터 문제를 좀 더 풀어볼 필요가 있을 것 같다.