2467. 용액 (Python)

2467번: 용액

 

풀이

 투 포인터(left와 right)를 사용하여 해결할 수 있다. 가장 처음과 끝에 포인터를 하나씩 두고 더한 결과에 따라서 포인터를 이동시킨다.

 

 두 포인터가 가리키고 있는 용액의 합이

1. 0일 경우
   -> 그대로 탐색을 종료한다.
   
   
2. 음수일 경우 
   -> 두 용액의 합을 0에 가깝게 하기 위해서는 더 작은 값을 가리키고 있는 left 포인터를 이동 시켜야 한다. 두 합이 음수일 경우는 더 작은 쪽의 값을 늘려야 0에 가까워 질 수 있기 때문이다.
   
   
3. 양수일 경우
   -> 두 용액의 합을 0에 가깝게 하기 위해서는 더 큰 값을 가리키고 있는 right 포인터를 이동 시켜야 한다. 두 합의 양수일 경우는 더 큰 쪽의 값을 줄여야 0에 가까워 질 수 있기 때문이다.

 

코드

if __name__ == '__main__':
    N = int(input())  # 전체 용액의 수
    nums = list(map(int, input().split()))  # 용액 리스트

    left, right = 0, N-1  # 투 포인터
    value = float('inf')  # 두 용액을 합쳤을 때 가장 0에 근접했을 때의 절댓값
    resLeft, resRight = 0, 0  # 출력해야 하는 두 용액의 특성값

    while left < right:
        tmp = nums[left] + nums[right]

        if abs(tmp) < value:  # 현재 두 용액의 합의 절댓값이 value보다 작을 경우 업데이트
            value = abs(tmp)
            resLeft, resRight = nums[left], nums[right]

        if tmp == 0:  # 합이 0일 경우에는 탐색 종료
            break
        elif tmp < 0:  # 음수일 경우에는 left 포인터를 이동시킨다.
            left += 1
        else:  # 양수일 경우에는 right 포인터를 이동시킨다.
            right -= 1

    print(resLeft, resRight)