[백준 - Python] 2467. 용액

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

 

코드

import sys
input = sys.stdin.readline

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

# 포인터 초기 설정
left_idx = 0
right_idx = n-1

ans = abs(liquids[left_idx] + liquids[right_idx])
ans_left = left_idx
ans_right = right_idx

while left_idx < right_idx:
    tmp = liquids[left_idx] + liquids[right_idx]

    if abs(tmp) < ans:
        ans_left = left_idx
        ans_right = right_idx
        ans = abs(tmp)
        if ans == 0:
            break

    if tmp < 0:
        left_idx += 1
    else:
        right_idx -= 1

print(liquids[ans_left], liquids[ans_right])

 

코드 설명

입력으로 주어지는 용액이 정렬되어 있고,

특정 수를 만족하는 두 개의 수를 구해야 함으로 투 포인터를 사용하면 유용하다.

 

두 개의 포인터를 배열의 양 끝에서 시작시키고, 초기 정답을 abs 변수에 설정한다.

 

포인터가 교차되지 않을동안, 두 용액을 혼합하는데

현재 저장된 혼합액의 특성값보다 더 작은 절댓값(0에 가까운 값)을 찾으면 갱신한다.

절댓값이 0이면 최적의 값이니 바로 종료한다.

 

합이 음수면, 더 큰 값을 얻기 위해 왼쪽 포인터를 오른쪽으로 이동시키고

합이 양수면, 더 작은 값을 얻기 위해 오른쪽 포인터를 왼쪽으로 이동시킨다.

 

배운 점

- 정렬된 배열에서 점진적으로 범위를 좁혀가면서 최적의 값을 탐색할 때에는 투 포인터를 사용하자