2470번 두 용액

문제 출처 : https://www.acmicpc.net/problem/2470

투포인터 관련 문제란 걸 몰랐다면 못 풀었을라나... 조금은 시간이 소요됐을 듯

사고과정

Brute force로 하면 O(n^2)이 나오는데 이건 아닐 거 아니야. 결국 합해서 0에 가깝게 되는 수를 찾는 것이기 때문에 투포인터를 하기에 앞서 정렬은 필수. ( 아마도? 아닌듯. ex 빗물트래핑)
아무튼 결국 이 문제에서는 0에 가깝게 만들기 위해서는 더했을 때 0보다 크다면 더 작은 수들을 더해야 하고 0보다 작다면 더 큰 수들을 더해야 한다.

수렴!의 아이디어

그래서 정렬된 투포인터를 이용할 수 있지 않을까?

import sys

N = int(sys.stdin.readline().rstrip("\n"))

li = list(map(int,sys.stdin.readline().rstrip("\n").split()))
li.sort()
left, right = 0, len(li)-1
result=float("inf")
first, second = 0, 0

while left< right :
    if result == 0 :
        break
    mixed=abs(li[left]+li[right])
    if mixed< result :
        result = mixed
        first, second = li[left], li[right]
    elif li[left]+li[right]>0 :
        right-=1
    elif li[left]+li[right]<0 :
        left+=1
print(first, second)

result==0 은 제해주는 가지치기를 통해 통과. 안하면 시간초과난다.

투 포인터 뿐만 아니라 이분 탐색으로도 풀수 있길래 공부삼아 적어본다.