[이분탐색] 백준 2470번 두 용액 with Python3 ★★

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

2470번: 두 용액

 

문제

정답 풀이

import sys
input = sys.stdin.readline

N = int(input())
liquid = [int(x) for x in input().split()]
liquid.sort()   #이분 탐색을 위해 정렬해준다.


left = 0
right = N - 1

answer = liquid[left] + liquid[right] #결국 최소 합 값을 충족하는 두 원소를 찾는 문제

al = left  #원하는 최소 answer을 얻었을때 그 합을 만드는 두 원소를 위한 인덱스
ar = right


while left < right:
    tmp = liquid[left] + liquid[right] #현재 값의 합
    
    if abs(tmp) < abs(answer):  #음의 정수가 있기에 min이 아닌 절대값으로 비교
        answer = tmp			#현재의 합이 전의 합보다 작다면 각 변수를 업데이트하고 진행
        al = left				
        ar = right
        if answer == 0:  #합이 0은 최저값이기에 바로 멈춰준다
            break
            
    if tmp < 0:     #합이 0보다 작다는 것은 음의 정수 값이 더욱 크다는것이기에
        left += 1   #왼쪽 인덱스를 1올려준다.
        
    else:           #vice versa
        right -= 1
        
        
print(liquid[al], liquid[ar])

출처:https://data-bank.tistory.com/29

 

해석

- 리스트에 용액들의 특성값을 입력합니다.

- 리스트를 오름차순으로 정렬합니다.

- left = 0, right = N - 1로 설정하고 이분탐색을 위해 left < right 일 때까지 while문을 반복합니다.

 

i ) 두 용액의 특성값의 합이 0인 경우

- while문을 break하고 결과를 출력합니다.

 

ii) 두 용액의 특성값의 합이 음수인 경우

- 음의 특성값의 절댓값이 양의 특성값의 절댓값보다 크기 때문에 left += 1 을 통해 두 용액의 특성값의 합이 0에 가까워 질 수 있도록 합니다.

 

iii) 두 용액의 특성값의 합이 양수인 경우

- 양의 특성값의 절댓값이 음의 특성값의 절댓값보다 크기 때문에 right -= 1를 통해 두 용액의 특성값의 합이 0에 가까워질 수 있도록 합니다.

- 만약 두 용액의 특성값의 합의 절댓값이 기존의 answer의 절댓값보다 작은 경우 answer 에 새로운 값을 입력하고 al =left, ar = right 을 통해 index를 저장해 줍니다. min을 사용하게 되면 -2와 1을 비교했을 때 answer 에 -2 가 입력되고 이는 오답이기 때문에 절댓값을 활용합니다.