백준 2470번 : 두 용액 in Python

2470번: 두 용액

 

www.acmicpc.net

이 문제는 여러 용액들 중 두 용액을 섞었을 때 두 용액의 특성값의 합의 절댓값이 가장 작은 경우를 구하는 문제이다.

이전의 두 수의 합 문제처럼, 이 문제 역시 단순하게 모든 용액의 쌍을 생각하기에는 오랜 시간이 걸리기 때문에 투 포인터를 이용해 문제를 해결한다.

두 수의 합 문제처럼, 먼저 각 용액의 특성값을 저장한 배열을 정렬한다. 그리고 두 포인터를 배열의 양 끝에 위치시키고 각 포인터가 가리키는 값의 합을 구한다. 만약 그 합이 0보다 작은 경우 왼쪽 포인터를 오른쪽으로 한 칸 이동시키고, 0보다 큰 경우 오른쪽 포인터를 왼쪽으로 한 칸 이동시킨다. 이는 이전의 두 수의 합 문제에서 x가 0인 경우에 문제를 해결하는 방법과 같다. 

하지만 이 문제에서는 두 포인터가 가리키는 값의 합이 0이 되는 경우를 구하는 게 아닌, 0과 가장 가까운 경우를 구해야 한다. 그래서 x 대신 두 값의 합의 절댓값이 최소일 때 두 값의 합을 저장하는 변수를 만들고, 이 변수의 절댓값보다 두 용액의 특성값의 합의 절댓값이 더 작은 경우에 변수의 값을 그 특성값의 합으로 한다. 그리고 출력해야 하는 결과는 이러한 경우 왼쪽 포인터가 가리키는 값과 오른쪽 포인터가 가리키는 값이므로 이를 변수에 저장한다.

이를 왼쪽 포인터와 오른쪽 포인터가 만날 때까지 반복하면 정렬 시간 O(n logn)과 탐색 시간 O(n) 안에 문제를 해결할 수 있다. 물론 이 탐색 시간을 줄이기 위해 포인터를 한 칸씩 옮기는 대신 이진 탐색을 이용해 다른 포인터의 값과 부호가 반대이고 절댓값이 가장 가까운 값의 포인터를 찾는다면 평균 탐색 시간을 O(log n)까지 줄일 수 있다. 하지만 이 문제는 정렬되지 않은 배열이 주어지기 때문에 정렬에 소모되는 시간으로 인해 전체 소요 시간에 큰 영향을 끼치지는 못한다. 그래서 이진 탐색은 따로 구현하지는 않았다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))
# 두 개의 포인터
l = 0
r = N-1
# 주어진 배열을 정렬한 뒤 투 포인터를 사용한다.
arr.sort()
# 출력할 결과를 저장할 변수들
min_left = arr[0]
min_right = arr[N-1]
# 두 용액의 특성값의 합의 절댓값이 가장 작은 경우 특성값의 합을 저장하는 변수 
min_var = arr[0]+arr[N-1]
while l < r:
    if abs(arr[l]+arr[r]) <= abs(min_var):
        min_var = arr[l]+arr[r]
        min_left = arr[l]
        min_right = arr[r]
    # 두 용액의 특성값의 합이 0인 경우 더 이상 while loop을 진행할 필요가 없다.
    if arr[l]+arr[r] == 0:
        break
    elif arr[l]+arr[r] < 0:
        l += 1
    else:
        r -= 1
print(min_left, min_right)