코테 준비/이진탐색

[백준] 2470. 두용액 (투 포인터)

imsmile2000 2023. 2. 7. 21:12

Two Pointers 알고리즘의 시간복잡도는 O(n)

n=int(input())
nlist=list(map(int,input().split()))
nlist.sort()
start=0
end=n-1
target=0 #0에 가까운
sum=[]
idx=[]
while start<end:
    s=nlist[start]+nlist[end]
    if s<target: #두용액의 합이 0보다 작으면
        idx.append(abs(s))
        sum.append((nlist[start],nlist[end])) #0
        start+= 1
    elif s>target: #두용액의 합이 0보다 작으면
        idx.append(abs(s))
        sum.append((nlist[start],nlist[end]))
        end-= 1
    else:
        idx.append(abs(s))
        sum.append((nlist[start],nlist[end]))
        break
k=idx.index(min(idx))
print(*sum[k])