[BaekJoon] 백준 알고리즘 2470번 / 두 용액 / 투포인터 / Python

문제

 

접근방법

투 포인터를 이용하여 효율적으로 용액을 선택해나가며 최적해를 찾는 알고리즘이다.

먼저 용액을 오름차순으로 정렬한 후 시작점 start와 끝점 end를 지정하고 두 용액의 합인 mix를 계산한다.

그리고 두 용액의 합의 절댓값이 더 작은 경우 ans와 res를 업데이트한다.

그리고 mix가 0보다 작으면 start를 증가시켜 더 큰 용액을 선택하고, 0보다 크면 end를 감소시켜 더 작은 용액을 선택한다.

mix가 0이면 루프를 종료한다.

 

코드

"""
1. 아이디어
    1) N(전체 용액 수)를 입력받아서 sort()를 통해 오름차순으로 정렬
    2) for문에서 포인터(start, end)를 이동시키며 최적값(용액 합 0) 도출

2. 시간복잡도
- N(전체 용액 수)는 최대 100,000 이다.
    1) 완전 탐색일 경우 => O(N^2), 시간초과!
    2) 투 포인터로 진행할 경우 => O(N), 가능!

3. 자료구조
    1) N(전체 용액수) 저장 int
    2) N개의 용액 리스트 int[]
    3) 두 용액의 특성값 int
    4) 두 용액 리스트 저장 []
"""

import sys
input = sys.stdin.readline

n = int(input())
liquid = sorted(list(map(int, input().split())))

start = 0
end = n-1
ans = liquid[start] + liquid[end]
res = (start, end)

while start < end:
    mix = liquid[start] + liquid[end]

    if abs(mix) < abs(ans):
        ans = mix
        res = (start, end)

    if mix < 0:
        start += 1
    elif mix > 0:
        end -= 1
    else:
        break

print(liquid[res[0]], liquid[res[1]])