[Python] 백준 2473번: 세 용액

https://www.acmicpc.net/problem/2473

2473번: 세 용액

 

import sys
input = sys.stdin.readline
INF = 3000000000


def getMinAbsFluids():
    minAbsSum = INF
    minAbsFluids = [0, 0, 0]

    for i in range(N-2):
        left, right = i + 1, N - 1

        while left < right:
            curSum = fluids[i] + fluids[left] + fluids[right]
            curAbsSum = abs(curSum)

            # minAbs 갱신
            if curAbsSum < minAbsSum:
                minAbsSum = curAbsSum
                minAbsFluids = [fluids[i], fluids[left], fluids[right]]

            # 0에 수렴하게끔 인덱스 조정
            if curSum > 0:
                right -= 1
            elif curSum < 0:
                left += 1
            else:
                return minAbsFluids

    return minAbsFluids


if __name__ == '__main__':
    N = int(input())
    fluids = list(map(int, input().split()))

    fluids.sort()

    minAbsFluids = getMinAbsFluids()
    print(*minAbsFluids)

 

3SUM 알고리즘을 이용했다.

 

우선 메인 함수를 호출하기에 앞서, 오름차순으로 정렬시켜야한다.

 

먼저 while문 안의 로직에 대해 언급하자면, 해당 로직은 left와 right을, 합이 0에 수렴하게끔 유도하여 줄여나가면서, 최소절대값(minAbsSum)과 그 때의 용액의 특성값들(minAbsFluids)을 갱신시킨다.

해당 while문을 i를 증가시키면서 0...N-3까지 진행하며, left는 i+1, right는 N-1로 초기화시킨다.

 

i=0일 때, 다음과 같이 진행된다.

 

 

그리고 INF를 2999999998으로 설정해야한다. 왜냐하면 특성값이 중복될 수 없으며, 1000000000이 특성값의 최대값이기 때문이다.

 

시간복잡도는 O(N^2)이다.