[백준] 2467 - 용액 (Python)

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

import sys
input = sys.stdin.readline

n = int(input())
d = list(map(int, input().split()))

p1, p2 = 0, n-1
a1, a2, res = 0, 0, float('inf')
while p1<p2:
    tmp = d[p1] + d[p2]
    if abs(tmp)<res:
        a1, a2 = d[p1], d[p2]
        if tmp==0:
            break
        res = abs(tmp)

	if tmp<0:
        p1 += 1
    else:
        p2 -= 1

1) 아이디어

전형적인 투포인터 문제이다. 주어진 용액의 특성값을 양 끝에서부터 비교한 후 정답을 출력한다.

2) 풀이

• while 루프를 포인터 p1과 p2를 용액의 특성값의 합(tmp)을 기준으로 업데이트하며 탐색한다. p1과 p2의 시작값을 각각 0과 n-1로 선언했으므로 p1은 왼쪽, p2는 오른쪽이다.
• 용액의 특성값은 오름차순으로 주어지므로 별도로 정렬할 필요가 없다.
• 초기값을 float('inf')로 res를 선언하고, 매 반복에서 res와 abs(tmp)를 비교한다. 현재의 특성값의 절대값이 res보다 작으면 a1과 a2, res를 업데이트한다.
• p1과 p2의 값이 같으면 안되므로 (=서로 다른 두 용액을 혼합해야 하므로) p1과 p2가 같아지면 탐색을 종료한다.
• 답이 여러개인 경우 임의의 답을 출력하면 되기 때문에, res의 절대값이 0인 경우 더이상 탐색할 필요가 없으므로 탈출한다.