[백준][이분탐색] 2473. 세 용액

2473. 세 용액

 

• 풀이
  • O(N^3)은 안되고 O(N^2)는 가능
  • 3개 골라야 하므로 → 1개를 고르고 나머지 2개를 이분 탐색

 

n=int(input())
lst=list(sorted(map(int,input().split())))
minV=float('inf')
answer=[]
flag=0

for i in range(n-2):
    l=i+1
    r=n-1

    while l<r:
        tmp=[lst[i],lst[l],lst[r]]
        if abs(sum(tmp)) <= minV:
            answer=tmp
            minV=abs(sum(tmp))

        if sum(tmp)<0:
            l+=1
        elif sum(tmp)>0:
            r-=1
        else:
            answer=tmp
            print(*answer)
            exit()

print(*answer)