2473. 세 용액 (Python)

2473번: 세 용액

 

풀이

 두 용액(링크)과 유사한 문제로 투 포인터를 사용하여 문제를 해결할 수 있다. 문제는 총 3개의 용액을 더해야 한다는 것인데 3개의 포인터를 두고 탐색하되 하나의 포인터는 움직이지 않고 고정시킨다. 그리고 나머지 2개의 포인터를 기존의 두 용액에서와 마찬가지로 합이 양수냐 음수냐에 따라서 이동시켜가며 0에 가까운 세 용액을 구하면 된다.

 

코드

if __name__ == '__main__':
    N = int(input())
    values = list(map(int, input().split())) # 용액의 특성값들
    values.sort() # 오름차순 정렬

    res = [0, 0, 0] # 특성값이 0에 가장 가까운 용액을 만들어내는 경우
    zero = float('inf') # 0에 가장 가까운 특성값의 절댓값

    for i in range(N - 2): # 하나의 포인터는 고정시킨다. 0 ~ N-3 까지
        left, right = i + 1, N - 1 # 이동시키는 두 개의 포인터 

        while left < right:
            threeSum = values[i] + values[left] + values[right] # 세 개의 용액을 더한다.

            if abs(threeSum) < zero: # 0에 가장 가까운 용액을 발견하면 답을 갱신한다.
                zero = abs(threeSum)
                res[0], res[1], res[2] = values[i], values[left], values[right]

            if threeSum > 0: # 세 용액의 합이 양수면 right 포인터를 이동시킨다.
                right -= 1
            else: # 그 외의 경우는 left 포인터를 이동시킨다.
                left += 1

    print(*res)