용액 ( 2467번 )

🧪 백준 2467번: 용액

2467번 문제 링크

---

📌 문제 설명

KOI 부설 과학연구소에서는 산성 용액과 알칼리성 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들고자 한다.
각 용액은 하나의 정수로 특성값을 가지며, 같은 양의 두 용액을 섞으면 합이 특성값이 된다.
정렬된 용액 리스트가 주어졌을 때, 두 용액을 선택하여 0에 가장 가까운 값을 만드는 조합을 찾아라.

---

🧠 핵심 아이디어

• 정렬된 리스트이기 때문에 투 포인터(Two Pointers) 알고리즘을 적용 가능
• 왼쪽 포인터는 음수 영역(알칼리성), 오른쪽 포인터는 양수 영역(산성)에서 시작하여
  두 값을 더하면서 0에 가까운 값을 탐색
• 현재 합이 0보다 크면 오른쪽 포인터를 왼쪽으로 이동, 작으면 왼쪽 포인터를 오른쪽으로 이동

---

✨ 나의 풀이

import sys

def _main(n_list):
    answer = [0, 0]
    result_sum = float('inf')
    l_idx, r_idx = 0, len(n_list) - 1
    while r_idx > l_idx:
        now_sum = n_list[l_idx] + n_list[r_idx]

        if result_sum > abs(now_sum):
            result_sum = abs(now_sum)
            answer = [n_list[l_idx], n_list[r_idx]]

        if now_sum > 0:
            r_idx -= 1
        else:
            l_idx += 1
            
    return ' '.join(list(map(str, answer)))

n = int(sys.stdin.readline().rstrip())
n_list = list(map(int, sys.stdin.readline().rstrip().split()))

print(_main(n_list))

---

⏱ 시간 복잡도 분석

 

while r_idx > l_idx : 투 포인터로 배열을 한 칸씩 이동하며 최적의 용액 조합을 찾아냄 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )