[Python] 백준 2467번 문제, 용액

<문제 링크>

 

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

2467번: 용액

 

---

<풀이>

 

문제 해결 방법은 산성 용액과 알칼리성 용액을 보유하고 있는데 두 가지 용액을 혼합해 0에 가까운 용액을 만드는 것이다. (산성-산성, 알칼리성-알칼리성 혼합 가능) (용액 리스트는 오름차순으로 정렬 되어 있음)

그래서 이분 탐색을 이용해 합이 0에 가까운 두 개의 수를 구하는 것이 목적이다.

두 가지 용액을 혼합한 값을 min_num에 저장하고 result은 두 용액의 특성값을 저장하는 리스트이다.

# 1: 이분 탐색은 left가 right와 같거나 커질 때 종료된다.

탐색 해볼 두 용액의 합인 sum_num를 구한 다음에

# 2: 0과의 차이는 음수, 양수 구분이 없기 때문에 abs()를 이용해 절댓값으로 min_num과 sum_num을 비교해서 새로운 특성값이 더 0에 가깝다면 result와 min_num을 업데이트 시켜준다.

# 3: sum_num이 음수라면 음수값이 큰 것이기 때문에 left + 1를 해주고, 양수라면 현재 양수값보다 작은 값을 사용하기 위해 right - 1를 해준다.

import sys

if __name__ == "__main__":
    N = int(input())
    arr = list(map(int, input().split()))
    result = [0, 0]
    min_num = sys.maxsize

    # 1
    left, right = 0, len(arr) - 1
    while left < right:
        sum_num = arr[left] + arr[right]

        # 2
        if abs(sum_num) < min_num:
            result[0], result[1] = arr[left], arr[right]
            min_num = abs(sum_num)

        # 3
        if sum_num < 0:
            left += 1
        elif sum_num > 0:
            right -= 1
        else:
            break

    print(*result)