[백준] 2470 두 용액

📌문제 링크

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

💡 문제 풀이

처음에는 간단히 음수 중 제일 작은 수와 양수 중 제일 큰 수를 더하면 되겠다! 라고 생각했다
근데 더 생각해보니 절댓값이 가장 비슷한 값끼리 더해줘야 0에 제일 가까워진다는 걸 깨달았다...
ex) -99 -2 -1 4 50 을 입력받으면 -2, 4를 더해줘야 함

그래서 대체 어떤 식으로 해야할까... 고민하다 결국 구글링함
역시 골드는 골드구나

검색해보니 투포인터를 사용하는 문제였다!
이분탐색과 원리는 똑같다

• 범위를 반씩 줄여나감 : 이분탐색
• 범위를 한 칸씩 줄여나감 : 투포인터

투포인터로 하나는 왼쪽에서(가장 작은 수부터) 하나는 오른쪽에서(가장 큰 수부터) 탐색하면서 더해주고, 가장 0에 가까운 값을 저장해주면 된다

📋코드

# 2470 두 용액
import sys
n = int(input())
liquid = list(map(int, sys.stdin.readline().split()))
liquid.sort()

# 구글링했습니다...
# 투포인터를 사용하라고 하더라고요,,
left = 0
right = n-1

result = []
total = abs(liquid[left] + liquid[right])

while left < right:
    tot = liquid[left] + liquid[right]
    # 처음에 등호 안넣어줬다가 indexError 나서 틀림...
    # n이 2일 때 등호가 없으면 result에 아무것도 안들어가서 틀린다
    if abs(tot) <= total:
        total = abs(tot)
        result = [liquid[left], liquid[right]]

    # 합이 음수라면 left를 늘려 더 큰 값을 더해 0에 가깝게 만든다
    if tot < 0:
        left += 1
    # 합이 양수라면 right를 줄여 더 작은 값을 더해 0에 가깝게 만든다
    else:
        right -= 1

print(result[0], result[1])

➕ 추가

코드 주석에서 등호 안넣어줘서 indexError났다고 썼는데 그냥 처음부터 result에 [liquid[left], liquid[right]] 넣으면 등호 안넣어도 된다

추가시간 없다고 해서 겁먹었는데 python3로도 통과했다