[python3] 백준 2470 풀이 ( 투포인터 )

문제의 목표는 두 용액을 선택하여 차이 값이 가장 적은 경우를 가지는 두 용액의 특성값을 출력해야한다.
입력으로 주어지는 N값은 100,000이다. 만약 모든 용액을 서로 비교한다고 가정한다면 100,000 * 100,000 경우의 수를 연산해야한다. 이러한 경우 연산 횟수가 너무 많아지기 때문에 완전 탐색으로 풀수가 없다.

따라서 다른 방법을 써야하는데 투포인터를 쓰는 방식을 생각해 볼 수 있다. 투 포인터는 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다. 따라서 보통은 i,j로 인덱스를 만들고 인덱스를 서로 1씩 증가 시켜가며 특정 합을 구할때도 많이 쓰인다. 이것과 비슷하게 이 문제를 처리할 수 있다. 다만 i,j를 서로 반대편에 놓고 값을 비교해가며 포인터를 옮겨주어야한다.

이러한 방식으로 데이터를 처리해주면 된다. 

N = int(input())
nums = list(map(int, input().split()))
nums.sort()
diff = 2000000000

L = 0
R = len(nums)-1

A, B = 0, 0
while L < R:
    ans = nums[L] + nums[R]
    if diff > abs(ans):
        diff = abs(ans)
        A = nums[L]
        B = nums[R]

    if ans > 0:
        R -= 1
    else:
        L += 1
print(A, B)