[백준 2470] 두 용액

문제

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

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

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

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

 

입력

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

 

출력

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

---

접근

N개의 용액 특성 중에서 2개를 선택해야한다. 이때 N은 최대 100,000의 값이 들어오기 때문에 모든 조합을 확인할 수 없다. 따라서 2개를 선택하는 탐색에서 시간을 줄일 필요가 있었다.

 

입력되는 용액의 특성들을 오름차순 정렬하고 왼쪽과 오른쪽에서 가운데로 좁혀오면서 탐색한다.

이때 0에 가까운 값을 찾아야하기 때문에 계산한 값을 절댓값으로 변환하여 비교하도록 한다.

 

N개에서 2개를 선택할 때 이진탐색을 고려해봐도 되는 것일까?

 

구현

- 입력받은 용액의 특성들을 오름차순으로 정렬한다.

- 이진탐색을 하기 위해서 정렬된 값을 사용해야한다.

N = int(input())
numbers = list(map(int, input().split()))
numbers = sorted(numbers)

- 초기에 0번째 인덱스와 N-1번째 인덱스의 값을 더하여 value에 저장한다.

- 이후 left와 right로 인덱스를 조작하여 얻어진 값들과 value를 비교한다.

- 현재 left와 right가 가리키는 값을 더하여 temp에 저장 후에 value와 비교한다.

- 비교할 때는 0에 가까운 값을 확인하기 위해 abs()를 활용한다.

- 만약 value가 0일 때는 바로 두 개의  수를 반환한다.

- 이후 temp가 0 미만일 때는 left를 증가시키고 아닐 때는 right를 감소시킨다.

def solve():
    left = 0
    right = N-1
    value = numbers[left] + numbers[right]
    pick_numbers = [numbers[left], numbers[right]]

    while left < right:
        temp = numbers[left] + numbers[right]
        if abs(value) > abs(temp):
            value = temp
            pick_numbers = [numbers[left], numbers[right]]
            if value == 0:
                return pick_numbers

        if temp < 0:
            left += 1
        else:
            right -= 1

    return pick_numbers

---

전체 코드

import sys
input = sys.stdin.readline

def solve():
    left = 0
    right = N-1
    value = numbers[left] + numbers[right]
    pick_numbers = [numbers[left], numbers[right]]

    while left < right:
        temp = numbers[left] + numbers[right]
        if abs(value) > abs(temp):
            value = temp
            pick_numbers = [numbers[left], numbers[right]]
            if value == 0:
                return pick_numbers

        if temp < 0:
            left += 1
        else:
            right -= 1

    return pick_numbers

N = int(input())
numbers = list(map(int, input().split()))
numbers = sorted(numbers)

answer = solve()
print(*answer)