[백준] 2467 용액 풀이 (Python)

문제 정보
문제 링크 : BOJ 2467 용액 
문제 난이도 : 골드 5
유형 : 투 포인터

1. 문제 접근 

이 문제는 입력으로 주어지는 용액들의 값이 이미 오름차순 정렬되어 있으며,
각 값의 크기 범위가 매우 넓어 모든 조합을 확인하는 완전 탐색 방식은 O(N²)라 비효율적이다.

 

두 용액의 합을 0에 가장 가깝게 만들어야 하므로,
정렬된 배열의 양 끝에서 시작해 두 값을 비교하고 조절해 나가는 투 포인터 방식이 가장 적합하다.

 

(1)
합이 0보다 크면 오른쪽 포인터를 왼쪽으로 이동시키고,
합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동시키는 방식으로
필요 없는 경우의 수를 빠르게 제거할 수 있다.

 

(2)
정렬된 상태에서는 두 인덱스를 동시에 조절하며 합을 좁혀가는 방식이 가장 효율적이기 때문에,
투 포인터가 이 문제에서 최적의 해법이라고 판단했다.

 

2. 문제 풀이 (Python)

import sys

input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split())) # 오름차순 정렬되어 있음

check = float('inf') # 절댓값 비교 
# 정답 초기화
ans1 = 0 
ans2 = 0 

# 이분 탐색
left = 0
right = N-1

while left < right : 
    total = arr[left] + arr[right]
    
    # 0보다 가까우면 
    if abs(total) < check : 
         check = abs(total)
         ans1 = arr[left]
         ans2 = arr[right]
    
    # 0 이면 반복문 중지
    if total == 0 :
        break
    # 인덱스 이동
    if total > 0 :
        right -=1
    else : 
        left +=1 

print(ans1,ans2, sep=" ")