투 포인터(백준 알고리즘 2470번)

♣ 투 포인터 복습

https://jy-deeplearning.tistory.com/132

투 포인터(백준 알고리즘 1644번)

 

♠ 백준 알고리즘 2470번

 

 

이 문제는 주어진 여러 가지 용액을 두 가지씩 골라 혼합했을 때, 가장 0에 가까운 용액의 특성값을 가지는 조합을 구하는 문제이다. 각 용액의 특성값은 음수와 양수 모두 가능하다. 

 

 

예제를 보면 다섯 가지 용액의 특성 중 두 개를 뽑아 더했을 때 가장 0에 가까운 조합이 -99, 98 이다. 

 

 

♠ 문제 해결 아이디어(투 포인터 사용)

이 문제를 해결하기 위해선 start를 0에서, end는 n-1 에서 시작하는 투 포인터를 사용할 수 있다. 이때 특성값에 따라 용액을 정렬해야 한다. start와 end로부터 용액을 하나씩  가져와서 더하면서 0에 가장 가까운 조합을 만들어내는 것이다. 

 

 

 

위의 예제를 적용하면, 받아온 용액의 특성들을 정렬한 뒤 start와 end 용액을 처음과 끝의 용액으로 설정하여 초기 특성값을 설정한다. 여기서는 0에 가장 가까운 특성값을 구하는 게 목표이므로 절댓값(abs)를 적용하여 0으로부터의 거리를 구하여 이를 초기 특성값으로 둔다. 

 

 

현재 사용한 용액은 start=0, end=n-1 이므로 while문을 시작할 때 current_sum은 -1이다. 현재의 용액 특성값의 절대값이 앞에서 설정한 특성값(min_sum)보다 작을 경우, 0에 더 가까운 것이기 때문에 min_sum을 현재 용액 특성값으로 갱신한다. 그렇지 않을 경우 기존의 min_sum을 유지한다. 

 

또한 현재 용액 특성값이 0보다 작을 경우, 0과의 거리를 더 좁혀주기 위해선 start를 1 늘려서 다음 용액을 선택함으로써 용액 특성값이 현재 용액 특성값보다 커지게 한다. 반대로 현재 용액 특성값이 0보다 클 경우, 0과의 거리를 좁혀주기 위해 end를 1 줄여서 다음 용액을 선택함으로써 용액 특성값이 현재 용액 특성값보다 작아지게 한다. 

 

즉 0을 중앙에 두고 start와 end를 점점 중앙으로 움직이면서 최대한 0과의 거리를 가깝게 하는 것이다. 

 

위의 예제를 이용하여 과정을 살피면 아래와 같다. 

start = 0, end = n-1
min_sum = abs(-99 + 98) = 1 

current_sum = -99 + 98 = -1 
abs(-1) = min_sum 이기 때문에 min_sum은 갱신되지 않는다. 
current_sum < 0 이므로 start += 1 

start = 1, end = 4 
current_sum = -2 + 98 = 96
abs(96) > min_sum 이기 때문에 min_sum은 갱신되지 않는다. 
current_sum > 0 이므로 end -=1

start = 1, end = 3 
current_sum = -2 + 4 = 2 
abs(2) > min_sum 이기 때문에 min_sum은 갱신되지 않는다. 
current_sum > 0 이므로 end-=1 

start = 1, end = 2 
current_sum = -2 + -1 = -3
abs(-3) > min_sum 이기 때문에 min_sum은 갱신되지 않는다. 
current_sum < 0이므로 start+=1 

start = 2, end = 2 
while문 종료

 

 

 

♠ 전체 코드 

import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
numbers = list(map(int, input().split()))
numbers = sorted(numbers)
start = 0 
end = n-1
ans = (numbers[start], numbers[end])
min_sum = abs(numbers[start]+numbers[end])

while start < end:
	current_sum = numbers[start] + numbers[end]
	
	if abs(current_sum) < min_sum:
		min_sum = abs(current_sum) 
		ans = (numbers[start], numbers[end])
		
	if current_sum < 0:
		start += 1 
		
	elif current_sum > 0:
		end -=1 
		
	else:
		break 
	
print(*sorted(ans))