백준 - 2470번 - 두 용액[파이썬(python)]

문제 출처 : https://www.acmicpc.net/problem/2470

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

 

구현 코드

from sys import stdin

n = int(input())
solution = list(map(int, stdin.readline().rstrip().split()))
solution.sort()
answer = 2e9+1 # 기준값
left = 0
right = n - 1
while left < right:
    
    total = solution[left] + solution[right]
    
    if abs(total) < answer:
        answer = abs(total)
        result = [solution[left], solution[right]]
    
    if total < 0:
        left += 1
    else:
        right -= 1
print(result[0], result[1])

 

문제 해설

위 문제는 투 포인터 문제이다.

먼저 문제에서 주어진 [-2, 4, -99, -1, 98]의 용액을 오름차순 정렬한다.

정렬된 solution 배열에는 [-99, -2, -1, 4, 98]이 되고 가장 왼쪽은 값이 가장 작은 용액, 가장 오른쪽은 값이 가장 큰 용액이 위치한다. 

 

먼저 값이 가장 작은 용액과 가장 큰용액을 섞고 섞은 값이 0보다 작다면 0에 가깝기 해주기 위해 왼쪽 인덱스를 하나 증가하여 섞어 값을 크게 만들어 주고, 만약 값이 0보다 크다면 0에 가깝게 해 주기 위해선 오른쪽 인덱스를 하나 줄여 섞은 용액의 값을 작게 만들어주면 된다.

이를 위해 초기의 left는 배열의 시작인 0 right는 배열의 끝인 n-1에 위치하여 시작한다.

이 과정을 더 이상 섞을 용액이 없을 때까지 반복하며 섞은 용액이 최솟값일 때마다 result 배열에 왼쪽 용액, 오른쪽 용액을 갱신시켜준다.

 

이해를 돕기 위해 위의 예시를 표로 정리하면 다음과 같다.

left	right	total	answer
0	4	solution[0]+solution[4] = -1	1
1	4	solution[1]+solution[4] = 96	1
1	3	solution[1]+solution[3] = 2	1
1	2	solution[1]+solution[2] = -3	1

 

이 방법을 사용하면 모든 용액이 음수나 양수로만 주어진 경우에도 최적해를 찾을 수 있다.