[BOJ]백준 2470번: 두 용액(Python)/Two Pointer

www.acmicpc.net/problem/2470

2470번: 두 용액

카카오 기출에 슬라이딩 윈도우를 이용한 문제가 종종 등장하길래 풀어본 투포인터 기초 문제

left, right 두 개의 포인터를 배열의 양 끝에 위치하도록 한 뒤

(left 포인터를 한 칸 이동한 것 vs right 포인터를 한 칸 이동한 것) 중 절댓값이 더 작은 쪽으로 이동하게끔 구현했다

n=int(input())
w=sorted(map(int,input().split()))

left=0
right=n-1
ans=[left,right]
m=abs(w[left]+w[right])

while(left<right):
    if abs(w[left]+w[right])<m:
        m=abs(w[left]+w[right])
        ans=[left,right]
        
    lleft = w[left+1]+w[right]
    rleft = w[left]+w[right-1]
    
    if abs(lleft)<abs(rleft):
        left+=1
    else:
        right-=1
        
print(str(w[ans[0]])+" "+str(w[ans[1]]))

Time Complexity: O(NlogN) = O(NlogN): 정렬하는데 걸린 시간 + O(N): 포인터를 이동시키는 총 시간