[백준]2467번 용액 - python파이썬

문제

 

 

이 문제를 처음 봤을 때는 대체 어떤 알고리즘을 활용해서 풀어야할 지 감이 쉽게 잡히지 않았다.

 

combination을 통해서 조합을 구해서 합의 최솟값을 구하는 방식으로 할까 했지만 문제를 보면 알다시피 범위가 굉장히 크기 때문에 시간초과가 발생할 확률이 높다.

 

그렇게 계속 고민하던 찰나에 어라..? 범위가 큰 상태에서 두수의 합을 구하는 거라면.... 투포인터 ??  하면서 불현듯 떠올랐다.

 

 

이 문제는 두개의 포인터를 배치해서 조건에 따라 포인터를 이동시켜가면서 답을 찾아주면 된다.

 

 

그리고 중요한 것은 투포인터 알고리즘을 적용하기전 하기전 꼭 오름차순 정렬을 해주는 것이다. (투포인터의 전제조건)

 

 

그래서 이 문제는 투포인터를 활용할 때 3가지 포인트를 생각해주면 된다.

 

 

1. 최솟값이 업데이트 될 때

 

최솟값이 업데이트 될 때는 어떤 때일까?

 

바로 왼쪽값과 오른쪽값의 합의 절댓값이 기존의 최솟값 보다 작을때이다.

 

= abs(arr[left] + arr[right]) < minimum

 

 

2. left 가 커져야할 때

 

 

left가 커져야될 때는 언제일까?

 

숫자가 담긴 배열이 오름차순 정렬되어있다고 가정할 때 arr[left] + arr[right] 가 0보다 작다면 현재 arr[left]의 절댓값이 arr[right] 보다 크다는 것을 의미한다.

 

0에 가깝게 만들어주기 위해서는 left를 +1 해주어 합의 절댓값을 작게 만들어 준다

 

 

 

3.right이 작아져야할 때

 

 

그렇다면 right이 작아져야할 때는 arr[right]의 절댓값이 arr[left] 보다 크다는 것을 의미한다. 그러므로 right에 -1을 해주며 범위를 조정해준다.

 

 

 

 

나의 코드

 

import sys

n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
arr.sort()

left = 0
right = n-1
mini = float('inf')
ans = []

while(left<right):
    total = arr[left]+arr[right]
    if abs(total) < mini:
        #절댓값으로 저장해주어야함
        mini = abs(total)
        ans = [arr[left],arr[right]]
    #합이 음수라면 음수의 정수가 더 작아져야하므로 left에 +1
    if total < 0:
        left += 1
    #합이 양수라면 양수의 정수가 더 작아져야하므로(0인경우는 안주어지므로 예외처리 안해도됨)
    else:
        right -= 1
    
    

print(*ans)