(Python) 백준 2467

백준 2467

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	33467	12632	9827	36.942%

문제

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

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

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

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

입력

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

출력

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

---

답안

import math
import sys

n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
global_min = math.inf
answer = []

def binary_search(pivot, start, end, result=-1):
    result = start if result == -1 else result
    if end <= start:
        return result
    mid = (start + end) // 2
    if abs(numbers[pivot]+numbers[mid]) < abs(numbers[pivot]+numbers[mid+1]):
        return binary_search(pivot, start, mid, mid)
    else:
        return binary_search(pivot, mid+1, end, mid+1)

for i in range(n-1):
    j = binary_search(i, i+1, n-1)
    local_min = abs(numbers[i] + numbers[j])
    if local_min < global_min:
        global_min = local_min
        answer = [numbers[i], numbers[j]]

print(answer[0], answer[1])

풀이

숫자의 배열이 주어졌을 때, 그 중 중복되지 않은 두 수의 합이 0에 가장 가까운 조합을 찾는 문제이다.

minimum_value = float('inf')
answer = []
for i in range(n):
		for j in range(i+1, n):
				if numbers[i]+numbers[j] < minimum_value:
						minimum_value = numbers[i]+numbers[j]
						answer = [i, j]
print(answer[0], answer[1])

물론 위와 같이 2중 반복문을 돌면 조합을 찾을 수 있겠지만, 숫자의 개수 n이 최대 10만이었으므로, 이와 같은 $O(n^2)$의 알고리즘으로는 시간 초과 판정을 받을 것 같다는 생각이 들었다.

(실제로 시간 초과 판정이 나는지 확인은 하지 않았지만 말이다)

그래서 문제에서 주어진 다른 조건을 이용해야 문제를 풀 수 있었고, 숫자가 정렬되어 있다는 점에 주목했다.

그래서 숫자가 정렬되어 있다는 점을 이용해, binary search를 하기로 했다.

각각의 숫자에 대해, 그 숫자와 더해졌을 때 0과 값이 가장 가까워지는 숫자를 binary search를 통해 구하면, $O(n \log n)$의 시간에 구할 수 있기 때문이다.

다만 할 일은 일반적인 binary search가 아니라, 가장 가까운 값을 찾는 search를 구현하기만 하면 되는 것이었다.

def binary_search(pivot, start, end, result=-1):
    result = start if result == -1 else result
    if end <= start:
        return result
    mid = (start + end) // 2
    if abs(numbers[pivot]+numbers[mid]) < abs(numbers[pivot]+numbers[mid+1]):
        return binary_search(pivot, start, mid, mid)
    else:
        return binary_search(pivot, mid+1, end, mid+1)

그래서 이와 같이 binary search를 구현했다.

result에, pivot과 더했을 때 0과 가장 가까워지는 숫자의 인덱스를 저장해두었고, 탐색이 종료되면 이를 반환한다.

result = start if result == -1 else result와 같은 라인을 추가한 이유는, 외부 반복문에서 i+1과 n-1이 같은 값이 되어 start와 end가 같은 값으로 호출되는 경우를 대비하기 위함이다.

더 우아한 해결책이 있을 것 같지만 그렇게 하더라도 어딘가에는 if 문이 있어야 하지 않을까? 해서 이정도로 마무리했다.

if abs(numbers[pivot]+numbers[mid]) < abs(numbers[pivot]+numbers[mid+1]):

이 문제에서 가장 중요한 부분은 이 부분의 조건식이다.

이 조건식을 조금 잘못 설정하더라도 여러 테스트케이스에 대해 성립하는 경우가 많기 때문에, 만약 본인이 “맞왜틀?” 상황이라면 이 조건식이 올바르게 작성되었는지, 경계값을 잘 체크했는지 다시 한 번 생각해보자.

이 글을 쓰는 필자도 경계값, 조건식 때문에 몇 번 틀렸다…

오늘의 교훈… binary search를 이용한 풀이를 할 때에는 테케 몇 개 맞는다고 좋아하지 말고 경계값 체크를 제대로 하자!