[백준] 14921번: 용액 합성하기

문제

백준 - 14921번: 용액 합성하기

분석

두 용액을 섞었을 때 가장 0에 가까운 특성값을 구하는 문제이다.

n의 크기는 10^5이기 때문에 모든 조합을 비교해서 볼 수 없다.
용액들이 오름차순으로 주어졌을 때, 이것을 이용해서 모든 조합을 고려하지 않아도 된다.
양쪽 끝에 가장 작은 것과 가장 큰 것이 놓여있을 텐데, 이 둘 중 절대값이 큰 것의 포인터를 움직이면 더했을 때 0에 가까워질 가능성이 있다. 반대로 말하면 절대값이 큰 것을 계속 고려할 필요가 없다는 뜻이다.

따라서 절대값이 더 큰 쪽의 포인터를 움직이면서 0에 가장 가까운 값을 찾는다.
비교할 때는 절대값을 비교하고 ans에는 부호가 있는 채로 넣는다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n = int(input())
liquids = list(map(int, input().split()))
i = 0
j = n-1
ans = sys.maxsize
while i < j:
    val = liquids[i]+liquids[j]
    if abs(ans) > abs(val):
        ans = val
    if abs(liquids[i]) > abs(liquids[j]):
        i += 1
    else:
        j -= 1
print(ans)

끝으로..

투 포인터 문제를 복습할 수 있는 문제였다.