[solved.ad 골드5] 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에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

예제

 

---

나의 풀이

이 문제를 모든 경우를 확인하는 브루트포스 방식으로 풀이하게 된다면 두 수의 합으로 나올 수 있는 경우를 모두 찾아야 하므로 O(n^2)가 소요될 것이다. 최악의 경우 10,000,000,000 이상의 반복이 필요할 것이다.

이 문제는 이분 탐색으로 풀이하였다.

1. 용액들을 정렬한다
2. 정렬된 용액들을 순차적으로 방문한다
3. 현재 방문한 용액이 10번째이고, -99의 값을 가지고 있다면 11번째부터 마지막 용액까지 중에 -99와 더했을 때 0을 만들 수 있는 +99와 가장 가까운 용액을 이분 탐색으로 찾는다
4. 3번에서 찾은 값이 +99와 가장 가까운 값이 아닐 수도 있다. 용액들이 정렬되어 있기 때문에 3번에서 찾은 값의 바로 옆에 있는 값을 같이 확인해봐야 한다
   • 아래 코드에서는 이분 탐색으로 찾은 값과 그 왼쪽의 값을 비교했다. 이분 탐색 과정에서 arr[mid] >= target 일 때 res를 갱신했으므로 찾은 값보다 더 오른쪽에 있는 값은 답이 아니게 된다
5. 용액들을 순차적으로 방문하며 3, 4번의 과정을 반복하다가 현재 가장 0과 가까워지는 수를 찾았다면 이를 갱신하며 최종적으로 가장 0과 가까운 두 수를 찾는다

 

전체 코드

n = int(input())
arr = sorted(map(int, input().split()))  # 정렬된 용액들


def binary_search(s, target):
    global arr
    res = n
    start, end = s, n - 1

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] >= target:
            res = mid
            end = mid - 1
        else:
            start = mid + 1
    return res


def solution():
    global arr
    v1, v2 = 0, 0
    best_sum = 10 ** 10
    for i in range(n):
        # 이분 탐색 수행: 현재 위치(i) 이후의 용액에서 탐색, 찾는 값은 (현재 용액 * -1)
        res = binary_search(i + 1, -arr[i])
        
        # 찾은 용액의 왼쪽 용액 확인
        if i + 1 <= res - 1 < n and abs(arr[i] + arr[res - 1]) < best_sum:
            best_sum = abs(arr[i] + arr[res - 1])
            v1, v2 = arr[i], arr[res - 1]

        # 찾은 용액 확인
        if i + 1 <= res < n and abs(arr[i] + arr[res]) < best_sum:
            best_sum = abs(arr[i] + arr[res])
            v1, v2 = arr[i], arr[res]
    
    print(v1, v2) # i 번째 용액을 확인할 때 i + 1번 용액부터 확인하기 때문에 항상 v1 <= v2 이다.


solution()

 

채점 결과