[Python] 백준 2467번: 용액(시간복잡도 2등)

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

2467번: 용액

import sys
input = sys.stdin.readline


def getMinAbsIndices():
    left, right = 0, N-1
    minAbsSum = 2000000001
    minAbsIndices = [-1, -1]

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

        if minAbsSum > curAbsSum:
            minAbsSum = curAbsSum
            minAbsIndices = [left, right]

        if curSum > 0:
            right -= 1
        else:
            left += 1

    return minAbsIndices


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

    nums.sort()

    i1, i2 = getMinAbsIndices()
    print(nums[i1], nums[i2])

우선 입력값을 오름차순으로 정렬시킨 뒤에, left, right라는 인덱스를 2개 두고 진행한다. left와 right의 합이 0에 가까워져야하므로, 현재의 합이 0보다 크면 right를 감소시키고, 아니라면 left를 증가시킨다. 이렇게 하는 것은 숫자가 정렬되어 있기 때문이다.

이런 식으로 O(N)에 해당하는 시간에 탐색을 하는데, 여기서 left, right의 합(curSum)의 절대값이 가장 작을 때, 그 때의 절대값(minAbsSum)과 두 개의 인덱스(minAbsIndices)를 저장하면 된다.

탐색이 끝난 뒤, 저장된 두 개의 인덱스인 minAbsIndices에 대해 출력해주면 된다.