[백준]2473 세용액 투포인터

풀이

https://sosoeasy.tistory.com/540 에서 숫자 두개의 특정합을 구했다면 이번문제는 세 숫자를 구한다. 풀이법은 다음과 같다.

1. 제일 왼쪽 숫자(first)를 잡는다

2. first 오른쪽 부분에서 투포인터를 적용한다

first	left			right
-2	6	-97	-6	98

3. 1. first를 전체에 대해서 O(N)번, 2.투포인터 부분이 O(N)이므로 O(N^2)으로 풀린다. (N은 최대 5000이므로)

 

소스코드

import sys

N=int(input())
L=list(map(int,sys.stdin.readline().split()))
L.sort()


min_sum = 9876543210
ans=[0,0,0]

for i in range(N-2):
    first = i
    left = i+1
    right = N-1
    while(left<right):
        now_sum = L[first]+L[left]+L[right]
        # print(left,right,now_sum)
        if abs(now_sum)<abs(min_sum):
            min_sum = now_sum
            ans[0]=first
            ans[1]=left
            ans[2]=right

        if now_sum<0:
            left+=1
        elif now_sum>0:
            right-=1
        else:
            break

print(L[ans[0]],L[ans[1]],L[ans[2]])