[코테]99클럽 코테 스터디 5일차 TIL 백준 2470 두 용액

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

 

이 문제는 투포인터 문제이다! 이분탐색과 상당히 비슷해보이지만, 다른 점이 있는데, 이분탐색이 중간점(mid)를 타겟 값과 계속해서 비교해 나가면서 범위를 좁혀나가는 방식이라면, 투포인터 문제는 말 그대로 움직이는 포인터(start, end)가 두개이다! 즉, 양 끝단에서 두 포인터를 움직여가면서 조건에 만족하는 답을 찾아내는 방식이라고 할 수 있다.

이 문제는 정렬된 용액의 특성값 리스트에서 두 포인터가 만날 때까지 현재 용액의 특성값의 합과 이전 용액의 특성값의 합의 크기를 비교해 나가면서 현재 용액의 특성값의 부호가 달라지는 조건에 따라 포인터를 움직이는 방식으로 풀었다. 

import sys

read = sys.stdin.readline

N = int(read())

drinks = list(map(int, read().split()))

drinks.sort()

start, end = 0, N - 1

target_sum = sys.maxsize

best_pair = (0,0)

while start < end:

    current_sum = drinks[start] + drinks[end]

    if abs(current_sum) < target_sum:

        target_sum = abs(current_sum)

        best_pair = (drinks[start], drinks[end])

    if current_sum < 0:

        start += 1

    else:

        end -= 1

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