[백준] 2473 - 세 용액

생각 흐름

1. 이전에 이런 문제랑 비슷한 걸로 이분 탐색 알고리즘을 쓰는 문제를 푼 기억이 난다.
2. 어떤 문제였는지 기억은 안 나지만 여기에 이분 탐색을 적용해보면 일단 두 수를 정한 다음 나머지 하나는 이분 탐색으로 찾는 방법이 있을 수 있다.
3. 그렇게 되면 $O(N^2logN)$인데, 일단 $N$이 5,000이라서 될 것 같긴 하다.
4. 하지만 파이썬은 안 될 수도 있다.
5. 하나를 정하고 두 수의 합을 조정하면 어떨까
6. 하나가 정해지면 두 수의 합이 정해진다. 그러면 나머지 부분에서 그 합에 가장 가까운 조합을 찾으면 된다.
7. 정렬하면 그 두 수를 찾기는 쉬워진다. 왜냐하면 투 포인터로 s와 e를 잡은 다음 타겟보다 작으면 s를 올리고 크면 e를 줄이면 되기 때문
8. 이렇게 하면 하나 정해서 돌리고, 그에 따른 나머지 부분에 대한 투포인터 탐색을 진행하므로 $O(N^2)$가 된다.

풀이

하나의 수를 정한다. 이를 target이라고 한다.
그 수의 오른쪽 부분에 대해서, 두 수의 합 rest가 -target과 가장 가깝도록 두 인덱스를 위치시킨다.
그 과정에서 abs(target + rest)가 최소가 되게 하는 세 인덱스를 갱신시킨다.

코드

import math
import sys


def solution():
    # 입력
    N, arr = get_input()
    
    # 정렬
    arr.sort()

    # 최소값 초기화 
    min_diff = math.inf
    answer = (0, 0, 0)

    # 한 인덱스를 i로 고정한다.
    for i in range(N - 2):
        # 나머지 부분의 시작과 끝 인덱스
        s = i + 1
        e = N - 1
        target = -arr[i]

        # s < e 인 동안 arr[s] + arr[e]가 -target 과 최대한 가까워지는 s와 e를 찾는다.
        while s < e:
            res = arr[s] + arr[e]
            now_diff = abs(res + arr[i])

            # 그 과정에서 보는 모든 경우에 대해서 항상 합의 절대값이 최소가 되는 세 수를 갱신한다.
            if min_diff > now_diff:
                min_diff = now_diff
                answer = arr[i], arr[s], arr[e]

            # 두 수의 합이 target 보다 작으면 s를 증가시킨다. 정렬되어 있기 때문에 s를 증가시키면 큰 수가 나온다.
            # 크면 e를 증가시킨다. 정렬되어 있기 때문에 e를 줄이면 작은 수가 나온다.
            if res < target:
                s += 1
            elif res > target:
                e -= 1
            else:
                # 두 수의 합이 target 과 같으면 이미 그 수의 합이 0이 됐다는 뜻이다.
                # 스페셜 저지이므로 바로 출력해줘도 무방하다.
                return arr[i], arr[s], arr[e]

    # 합의 절대값이 최소가 되는 세 수의 조합을 리턴한다.
    # 여기까지 왔다면 절대 0은 안 나온다는 말이다.
    return answer


def get_input():
    N = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    return N, arr


sys.stdout.write("%d %d %d" % solution())