[백준] 용액 - 파이썬 Python

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

 

개념: 투 포인터, 이분탐색

 

• N은 2 이상 100,000 이하의 정수이므로 순차탐색(이중 for문)은 최악의 경우 시간복잡도 O(N^2)가 1초를 넘어간다. 
• 게다가 용액의 특성값이 정렬된 순서로 주어진다.

풀이

• 시간복잡도: O(N)

1. 0과 n-1을 투포인터로 지정한다.
2. 합이 0에 가까운 구간을 탐색한다.
   1. value는 현재 특성값의 합과 이전 값을 비교하기 위한 변수로, 우선 나올 수 있는 최대값인 2,000,000,000으로 설정했다.
   2. 비교했을때, 현재 특성값의 합이 더 작다면 value, x, y값들을 업데이트 해준다.
   3. 동시에 포인터를 조절해주기 위해 현재 특성값의 합이 0 이하면 왼쪽 포인터를 +1, 0보다 크면 오른쪽 포인터를 -1 만큼 움직인다.

n = int(input())
data = list(map(int, input().split()))

left = 0
right = n - 1
value = 2000000000
x, y = 0, 0

while left<right:
    cur_sum = data[left] + data[right]
    
    if abs(cur_sum) <= value:
        value = abs(cur_sum)
        x = data[left]
        y = data[right]
        
    if cur_sum <= 0:
        left += 1
    
    else:
        right -= 1

print(x, y)