[2473] 세 용액 in python

https://www.acmicpc.net/problem/2473

투 포인터를 활용하여 풀어야했던 문제!

 

빡구현으로 풀게 되면

당연히 시간초과가 발생한다.

 

 

이분 탐색을 이용하려면

일단 오름차순으로 리스트를 정렬한 뒤

투 포인터를 사용해야 한다.

 

세 용액의 합이 음수이면 left 포인터가 오른쪽으로 1칸 이동하고

양수이면 right 포인터가 왼쪽으로 1칸 이동한다.

 

left 포인터가 오른쪽으로 움직이거나

right 포인터가 왼쪽으로 움직이게 되면 

합의 절댓값이 0에 가까워진다.

 

 

지금 같은 경우에는 left의 위치가 i+1,

right의 위치는 평소대로 n-1에 위치해있다.

 

왜냐하면

이 문제에서는 두 용액이 아닌 세 용액의 합을 더해줘야 하기 때문이다.

따라서 array[i]의 값은 0부터 n-2-1까지만 이동한다.

n-2, n-1번째 위치에는 left, right의 포인터가 위치해있어야 하기 때문.

 

세 용액의 합이 여태컷 앞에서 구했던,

직전까지 가장 최소의 합을 지니고 있었던 값 temp 보다 작으면

answer에 세 용액의 각각의 값을 업데이트 해주고

temp에는 현재 최소의 값, sumValue값을 넣어준다. (절댓값으로)

 

그리고 left, right 값을 각각 조정해주는데

만약 sumValue의 값이 0이면

0에 가까운 값이 아닌 딱 0이라는 값이 되었기 때문에

for문을 바로 종료해도 된다.

 

출력 조건에서 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는

아무거나 출력하라고 했기 때문에

for문을 종료하면 된다. 

 

 

 

* 기억해야 할 점 *

투 포인터를 이용하여

두개의 값이 아닌 세 개의 값의 합을

비교할 수 있다. 

 

현재 위치를 기준으로 for문을 밖에서 돌려주고

for문 안에서는 left, right의 위치를

값에 따라 변경하는 while 문을 돌려주면 된다.

 

 

'''
산성 - 양의 정수
알칼리성 - 음의 정수
'''
import sys

n = int(input())
array = sorted(list(map(int, input().split())))
answer = []
temp = sys.maxsize
for i in range(n - 2):
    left = i + 1
    right = n - 1
    while left < right:
        sumValue = array[i] + array[left] + array[right]
        if abs(sumValue) < temp:
            answer = [array[i], array[left], array[right]]
            temp = abs(sumValue)
        if sumValue < 0:
            left += 1
        elif sumValue > 0:
            right -= 1
        else:
            break

print(*answer)