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

2473. 세 용액

2473번: 세 용액

 

• 내 풀이: fail
  •  n개의 원소 중 임의의 3개를 뽑아서 합을 구하는 방식으로 하게 되면 시간복잡도가 O(n^3)까지 올라감
  •  →투 포인터를 사용해서 O(n^2)으로 풀어야 통과할 수 있다. 
  • minV값을 int(1e9) 써서 틀린 거였음 ㅡㅡ.......
    • -> float('inf') 로 사용해야 통과....... 

import sys
input=sys.stdin.readline

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

def solve(n):
    global minV
    global answer
    tmp=[]
  
    for i in range(n-2):
        left=i+1
        right=n-1
  
        while left<right:
            tmp=[lst[i],lst[left],lst[right]]
    
            if minV>abs(sum(tmp)):
                minV=abs(sum(tmp))
                answer=tmp[:]
              
            if sum(tmp) >0:
                right-=1
            elif sum(tmp) <0: 
                left+=1
            else: #0이면
                answer=tmp[:]
                return answer
    return answer

answer=solve(n)
print(*sorted(answer))

 

•