[알고리즘] 백준 파이썬 2467 용액

📍 문제 탐색하기

용액 문제는 주어진 용액들 중 두 개의 용액을 선택하여 특성값의 합이 0에 가장 가까운 조합을 찾는 문제입니다.
입력으로 주어진 용액들은 이미 오름차순 정렬되어 있으며, 음수와 양수로 구성되어 있을 수도 있습니다.
이 문제의 목표는 시간 복잡도를 줄이기 위해 투 포인터(Two Pointers) 기법을 사용하여 빠르게 해결하는 것입니다.

---

문제 조건

• 용액의 개수 N: 2≤N≤100,000
• 용액의 특성값 범위: −1,000,000,000≤ai≤1,000,000,000​
• 입력 데이터 특징:
  • 오름차순 정렬되어 주어짐.
  • 중복된 특성값이 없음.
  • 산성 용액과 알칼리성 용액만으로도 조합 가능.

---

가능한 시간 복잡도

• 브루트포스(완전 탐색): O(N^2)→ N이 최대 100,000이므로 시간 초과.
• 투 포인터(Two Pointers): O(N)
  • 리스트가 정렬된 상태에서 양쪽 끝에서 중앙으로 접근하면서 탐색 수행.
  • 따라서 O(N)으로 해결 가능.

---

📍 코드 설계하기

1. 입력 처리
   • 용액 리스트를 입력받아 정렬된 상태로 유지.
2. 투 포인터 탐색 적용
   • 왼쪽 인덱스 left=0, 오른쪽 인덱스 right=N−1.
   • 두 개의 용액을 섞어 합의 절댓값을 확인.
   • 합이 0보다 크면 오른쪽 포인터를 왼쪽으로 이동.
   • 합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동.
   • 가장 0에 가까운 값을 갱신.
3. 결과 출력
   • 최적의 두 용액 값을 오름차순으로 출력.

---

📍 시도 회차 및 수정 사항

1. 초기 구현
   • 단순한 이중 반복문 접근 O(N2)O(N^2)O(N2), 시간 초과 발생.
   • 투 포인터로 변경하여 성능 개선.
2. 투 포인터 적용 후
   • 합이 0에 가까운 조합을 빠르게 찾을 수 있도록 최적화.

---

📍 코드 구현

import sys
input = sys.stdin.readline

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

left, right = 0, N - 1
closest_sum = float('inf')
result = (0, 0)

while left < right:
    total = liquids[left] + liquids[right]

    if abs(total) < abs(closest_sum):
        closest_sum = total
        result = (liquids[left], liquids[right])

    if total < 0:
        left += 1
    else:
        right -= 1

print(result[0], result[1])