[BOJ] 2473 세 용액 (Python)

문제

N개의 용액이 주어지면, 3개를 골라 합이 최대한 0에 가깝게 하는 문제

풀이 전략

Binary Search

두 개의 포인터를 이용해 풀 수 있는 문제입니다.

처음에는 브루트포스 알고리즘으로 풀어보려 했는데,
$O(n^3)$ 의 시간복잡도가 필요해 시간 초과가 발생할 듯 하여 시도해보지 않았습니다.

문제를 풀 때 이용한 전략은 다음과 같습니다.

• 하나의 값을 고정해두고, 나머지 두 개의 값을 포인터를 이용해 0에 가까워지도록 이동시킵니다.
• 이 때 세 값의 합인 cur_sum 변수의 값이 0 초과이면 포인터를 왼쪽으로, 미만이면 포인터를 오른쪽으로 포인터를 움직이고, 0이면 값들을 출력하고 프로그램을 종료합니다.

정렬에 $O(n \log n)$의 시간이 걸리고, 탐색에 $O(n^2)$의 시간이 걸리므로, exponential time에 문제를 해결할 수 있습니다.

구현

import sys

if __name__ == "__main__":
	input = sys.stdin.readline

	n = int(input())
	array = sorted(list(map(int, input().split())))

	answer = 2147000000
	sol_candi = []

	for i in range(n-2):
    	key = array[i]
    	left_pointer = i+1
    	right_pointer = n-1
    	while left_pointer < right_pointer:
        	cur_sum = key + array[left_pointer] + array[right_pointer]
            
        	if abs(cur_sum) <= abs(answer):
            	sol_candi = [key, array[left_pointer], array[right_pointer]]
            answer = key + lst[left_pointer] + array[right_pointer]
            
        	if cur_sum < 0:
            	left_pointer += 1
        	elif cur_sum > 0:
            	right_pointer -= 1
        	else:
            	print(*sol_candi)
            	sys.exit()

print(*sol_candi)