[BOJ2473] 세 용액

전체 용액의 수: N

용액의 특성값의 범위는 광범위한 상태이다.

이를 일일이 확인하면 TLE가 되므로, 이분 탐색이 낫다.

이분 탐색은 왼쪽과 오른쪽을 서서히 중앙으로 모이게 만드는 전략이다.

하지만, 이분 탐색은 두 용액이면 유용하겠지만, 세 용액은 오히려 더 힘든 상태이다.

그래서 사용하는 것이 투 포인터이다.

 

투 포인터에 관한 설명은 geeksforgeeks에 잘 되어 있다.

https://www.geeksforgeeks.org/two-pointers-technique/

Two Pointers Technique - GeeksforGeeks

import sys

def main():
    N = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    arr.sort()
    ans = [0, 0, 0]
    min_diff = 3000000000
    for i in range(N-2):
        l, r = i+1, N-1
        while l < r:
            tmp = arr[i] + arr[l] + arr[r]
            if abs(tmp) < min_diff:
                min_diff = abs(tmp)
                ans = [arr[i], arr[l], arr[r]]
            if tmp < 0:
                l += 1
            else:
                r -= 1
    print(*ans)

if __name__ == '__main__':
    main()