2470번 두 용액

문제

https://www.acmicpc.net/problem/2470
KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.
산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

풀이

이 문제는 투 포인터 문제이다.
반복문을 돌며 두 개의 수를 더하고 비교했을 때, 절대값이 작은 수를 갱신하면서 최저값을 찾으면 된다.

투 포인터(Two Pointer)

리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘

양 끝단에 있는 left, right 두 개의 포인터를 한 칸씩 이동하면서 알맞은 값을 찾는 것이다. '특정한 합을 가지는 부분 연속 수열' 문제에 적용 가능하다.

이분 탐색의 경우 mid를 활용해 매 연산마다 탐색하는 범위를 절반 씩 좁혀 나간다는 점에서 차이가 있다.

약간의 이슈라면 입력이 10억까지 주어지는데 변수 min_에 최대값으로 1e9로 초기화하면 min_값 보다 더 큰 수로 인풋값이 들어오기 때문에 에러가 난다. 1e12이나 sys.maxsize로 초기화 하자.

전체코드

import sys
sys.stdin = open('2470.txt','r')
input = sys.stdin.readline

n = int(input())
nums = list(map(int,input().split()))
# 오름차순 정렬
nums.sort()

def twoPointer():
    # 배열의 양 끝단 인덱스 설정
    left = 0
    right = n - 1
    min_ = sys.maxsize

    while left < right:
        # 현재 지점의 합
        current = nums[left] + nums[right]

        # 만약 현재 지점의 합이 더 0에 가깝다면
        if abs(current) < min_:
            # 갱신하기
            min_ = abs(current)
            min_left = nums[left]
            min_right = nums[right]
        
        # 현재 지점의 합이 음수라면 
        if current < 0:
            # 왼쪽을 오른쪽으로 한 칸 옮겨서 0에 가깝게 만들기
            left += 1
        else:
            right -= 1

    return min_left, min_right

print(*twoPointer())