문제

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

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

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

코드

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()


# 맨왼쪽과 맨끝 인덱스로 left right을 지정 후 왼쪽에서 한칸, 오른쪽에서 한칸 옮겨 그 절대값의 합이 더 적은쪽으로
# 인덱스를 한칸 옮김

left = 0
right = n - 1
ans = 2000000000 #입력 조건 중 최대값을 미리 지정
idx = (0,0)
while left <= right:
    if ans >= abs(arr[left] + arr[right]):
        ans = abs(arr[left] + arr[right]) #절대값이 더 적은 것을 저장 절대값이 작다 -> 0에 근접한다.
        idx = (left, right) #인덱스 저장
    if left + 1 != right:
        leftwindow = abs(arr[left+1] + arr[right]) #한칸씩 옮겼을 때 더 절대값이 적은 쪽으로 이동
        rightwindow = abs(arr[left] + arr[right-1])
    else:
        break

    if leftwindow <= rightwindow:
        left += 1
    else:
        right -= 1

print(arr[idx[0]], arr[idx[1]])

설명

0에 근접한 값을 찾기 위해 left, right를 배열의 맨 끝 인덱스로 지정하고 최댓값을 저장할 ans는 입력 조건의 최댓값인 2,000,000,000을 저장하고 각각 반복을 할 때마다 left, right 번째 원소를 합하고 그 절댓값과 비교해 더 적은 것을 ans에 값과 그 인덱스를 저장해주었다. 그리고 left에서 1칸 옮기거나 right에서 1칸 옮겼을 때의 값 중 더 적은 값을 가진 쪽으로 한 칸 옮긴다. 반복문이 종료되면 idx에 저장된 인덱스의 값들을 출력해준다.