[BOJ/백준] 2467번 용액 - Python/파이썬 [해설/풀이]

📌 문제

---

📝 입력

---

💻 출력

---

📖 예제 입출력

---

📌 풀이

---

📖 해설

---

시간복잡도를 고려해야하는 문제로,
단순 선형탐색을 이용하면 시간초과에 걸린다.
이진탐색을 활용하여 시간초과를 피할 수 있어야 한다.

단순히 최소값을 찾는 것이 아닌, 합계가 0에 가까운 두 값을 찾아야 하므로,
두 값의 합계의 절대값이 최소인 두 값을 찾는다.

정렬된 배열이 주어지므로,
별도의 두 값을 선택하는 모든 경우의 수를 따질 필요는 없다.

💻 전체코드

---

N = int(input())
liquids = list(map(int, input().split()))

min_val = float('inf')
answer = [float('inf'), float('inf')]
left, right = 0, N - 1
while left < right:
    if abs(liquids[left] + liquids[right]) < min_val:
        min_val = abs(liquids[left] + liquids[right])
        answer = [liquids[left], liquids[right]]

    if liquids[left] + liquids[right] < 0:
        left += 1
    else:
        right -= 1
print(*answer)