https://www.acmicpc.net/problem/2473
시간 1초, 메모리 256MB
input :
- N (3 <= N <= 5000)
- N개의 용액 특성값(-1,000,000,000 <= 용액 <= 1,000,000,000)
output :
- 0에 가장 가까운 용액을 만들어내는 세 용액의 특성값을 출력
- 특성값의 오름차순으로 출력
조건 :
- 산성 용액의 특성값은 1부터 1,000,000,000
- 알칼리성 용액의 특성값은 -1부터 -1,000,000,000
이분 탐색을 해야 하나 생각을 했는데 그럴려면 하나의 용액은 고정을 시켜야 한다. 그리고 고정은 또 어떻게 시킬건지 이게 문제였다.
그냥 3개를 뽑는다고 생각하면 410억의 연산이 필요해서 불가능하다.
탐색을 해야 하는데 어떻게 해야 할까..
예상치도 않았는데 그냥 완전탐색을 이용해서 하나의 용액을 고정시키고 다른 두 용액을 찾는 것이었다. 생각보다는 허탈했는데 이 방법을 보니까 글킨 하네 하고 수긍했다.
우선적으로 정렬을 해줘야 한다. 알칼리성은 음수이고, 산성은 양수이니까 정렬을 통해 얻을 수 있는 이점이 존재한다.
그리고 3가지 용액중 첫 용액은 언제나 i번째 용액으로 고정을 시킨다. for문이 0번째 부터 n - 2번째 까지 돈다면 모든 경우의 수를 다 보는 것이기 때문에 중간 지점에서 앞 부분의 용액을 못 보는 경우는 존재하지 않는다.
for문을 수행 하며 그 내부에선 투 포인터를 사용하는데 이전에 가지고 있던 값과 현재 용액들의 합을 비교해야 한다. 0과 가까운것은 절댓값을 사용하는 것이 편하다.
temp, compare 값들에 절대값을 씌운 후 compare - temp 한 것이 양수라면 temp가 0에 더 가까운 것으로 교체를 해야 한다.
그리고 temp 값을 0과 비교해서 0보다 크다면 right -= 1 양수의 값을 줄이는 방안으로 0에 더 가깝게 만들고
작다면 left += 1을 통해 음수의 값을 작게 해서 0에 더 가깝게 한다.
import sys
from collections import deque
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
data.sort()
ans = deque([(float('INF'), 0, 0, 0)])
for i in range(n - 2):
left = i + 1
right = len(data) - 1
while left < right:
temp = data[i] + data[left] + data[right]
compare, prev_i, prev_left, prev_right = ans.popleft()
if abs(compare) > abs(temp):
ans.append((temp, i, left, right))
else:
ans.append((compare, prev_i, prev_left, prev_right))
if temp > 0:
right -= 1
else:
left += 1
val, i, left, right = ans.popleft()
print(f"{data[i]} {data[left]} {data[right]}")
