세 용액

• 두 용액 과 똑같은 설정이지만 이번에는 두 용액이 아닌 세 용액을 섞어서 0에 가까운 용액을 만들어야 한다. 
  • 문제 출처는 KOI 2010인데, 두 용액은 중등부, 이 문제는 고등부 문제이다
• 두 용액에서 투 포인터를 사용해서 정렬된 배열에서 합이 X에 가까운 두 수를 O(n)에 찾는 방법을 이미 설명했다. 용액이 세개일때는 이것을 n번 반복하면 된다. 즉 모든 i에 대해서, arr[i]를 용액에 넣기로 고정하고, arr[i+1:N]에서 합이 -arr[i]에 가까운 두 수를 O(n)에 찾으면 된다. 처음에 정렬하는데에 O(nlogn)이 걸리고, 탐색에는 O(n^2)이 걸려서 총 시간복잡도가 O(n^2)이 된다.
  • 두 용액에서는 합이 0에 가까운 두 수를, 절대값을 기준으로 정렬해서 푸는 방법도 소개했다. 하지만 여기에서는 그 방법은 쓸수 없다. 그 방법으로 합이 X에 가까운 두 수를 구하는 것 자체는 가능하지만, X값이 바뀔때마다 다시 정렬을 해야 하기 때문에 O(n^2logn)으로 시간복잡도가 늘어난다.
• 특이한 점은, 만약 계산 도중에 합이 0이 되는 세 용액을 찾는다면 거기에서 중단하는 로직을 넣느냐 마느냐로 시간 차이가 엄청 크게 난다. 그런 경우에는 더 이상 찾을 필요가 없으니까 거기서 중단해도 되는 것은 당연하지만, 보통 이런식의 특정 데이터에서만 유용한 최적화는 굳이 구현하지 않는다. 이 문제의 경우 테스트 데이터에 합이 0이 되는 세 용액이 없는 경우에는 저 최적화가 아무 의미 없고, 정상적인 데이터셋이라면 그런 데이터가 당연히 포함이 되어있으리라 예상하기 때문이다. 하지만 이 문제에서는 큰 사이즈의 테스트셋에는 전부다 합이 0이 되는 경우가 포함되어 있는지 저 로직을 넣자마자 시간이 거의 절반으로 줄었다.
• 그 외에도 굳이 더 최적화를 하자면 할 여지는 더 많다. 예를 들어서 a[i]를 용액에 넣기로 고정하고 나머지 a[j]와 a[k]를 i<j<k 범위에서 투 포인터로 찾는다고 할때, a[i]가 0보다 커지면 거기서 루프를 중단해도 된다. a[i]>0이면 합이 0에 가장 가까운 것은 계산할 필요도 없이 a[i]+a[i+1]+a[i+2] 이다. 그리고 거기서 i가 더 커지면 가장 0에 가까운 합도 더 커지므로 (a[i+1]+a[i+2]+a[i+3] > a[i]+a[i+1]+a[i+2] > 0) 굳이 i를 더 늘려나갈 필요도 없다. 하지만 굳이 이렇게까지 상수 최적화를 할 필요는 없어서 구현은 안했다

"""Solution code for "BOJ 2473. 세 용액".

- Problem link: https://www.acmicpc.net/problem/2473
- Solution link: http://www.teferi.net/ps/problems/boj/2473

Tags: [TwoPointer]
"""

INF = float('inf')


def main():
    N = int(input())
    nums = [int(x) for x in input().split()]

    nums.sort()
    min_abs_sum = INF
    for _ in range(N - 2):
        num = nums.pop()
        from_left, from_right = iter(nums), reversed(nums)
        left, right = next(from_left), next(from_right)
        for _ in range(len(nums) - 1):
            sum_val = num + left + right
            if abs(sum_val) < min_abs_sum:
                min_abs_sum = abs(sum_val)
                answer = (left, right, num)                
            if sum_val < 0:
                left = next(from_left)
            else:
                right = next(from_right)
        if min_abs_sum == 0:
            break

    print(*answer)


if __name__ == '__main__':
    main()