[백준/Python] 2470번: 두 용액

문제

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

2470번: 두 용액

---

문제 요약

N개의 용액 특성 값들을 입력 받고, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 출력한다.

 

용액의 특성값의 범위는 -1000000000 ~ 1000000000이다.

---

코드

n = int(input())

arr = sorted(list(map(int, input().split())))

left = 0
right = n - 1

res_mix = 2000000000 # 두 용액을 혼합한 용액 중 0에 가장 가까운 특성값 (초기: 두 용액을 혼합했을 때 나올 수 있는 최대 특성값)
res_left = 0 # res_mix를 만드는 두 용액 중 작은 특성값을 가진 용액의 인덱스 (초기: 가장 작은 특성값을 가진 용액 인덱스)
res_right = n - 1 # res_mix를 만드는 두 용액 중 큰 특성값을 가진 용액의 인덱스 (초기: 가장 큰 특성값을 가진 용액 인덱스)

# 투 포인터 방식으로 리스트의 양쪽 끝부터 0에 가장 가까운 혼합 용액 탐색
while left < right: # 같은 용액을 두 번 혼합할 수 없으므로 left == right는 불가
    tmp = arr[left] + arr[right] # 두 용액을 혼합한 용액의 특성값

    # res_mix보다 더 0에 가까운 특성값을 발견했다면 res_mix, res_left, res_right 갱신
    if res_mix > abs(tmp):
        res_mix = abs(tmp)
        res_left = left
        res_right = right

     
    if tmp > 0: # 혼합 용액의 특성값이 0보다 크면
        right -= 1 # 0에 더 가까운 경우를 탐색하기 위해 다음으로 작은 특성값을 가진 용액을 가리키게 한다.
    else: # 혼합 용액의 특성값이 0보다 작으면
        left += 1 # 0에 더 가까운 경우를 탐색하기 위해 다음으로 큰 특성값을 가진 용액을 가리키게 한다.

print(arr[res_left], arr[res_right])

---

코드 설명

1. 입력 받은 n개의 용액 특성값들을 리스트 arr에 저장하고 투포인터 방식의 탐색을 위해 오름차순 정렬한다.

 

2. 인덱스를 저장한 두 개의 포인터가 arr의 양쪽 끝 값을 가리키게 하고, 가리키는 두 값을 더해서 0에 더 가까운 값이 있는지 탐색한다.

 

2 - 1. 두 값의 합의 절댓값이 이전까지 발견된 값보다 0에 더 가까우면 갱신한다.

 

2 - 2. 두 값의 합이 0보다 크면 다음 탐색은 더 작은 값을 탐색하기 위해 오른쪽 포인터의 값을 1 감소시킨다.

 

2 - 2. 두 값의 합이 0보다 작거나 같으면 다음 탐색은 더 큰 값을 탐색하기 위해 왼쪽 포인터의 값을 1 증가시킨다.

 

3. 탐색이 종료된 후, 0에 가장 가까운 특성값을 가진 혼합 용액을 만들기 위해 필요한 두 용액의 특성값을 출력한다.