[Python] 백준 2470번 두 용액 문제

백준 2470번 두 용액 문제를 접근하는데 이진탐색으로 못 풀고 투 포인터라는 방법으로 풀었다. 

2470번: 두 용액

---

 

나의 풀이

선형탐색으로는 O(N^2)으로 시간초과가 될 것이니, 이분탐색이나 투포인터라는 알리고즘?으로 풀어야한다. 절대값이 0에 가까운 두 값의 조합을 찾기 위해서 두 조합의 합이 음수이면 왼쪽 원소의 절대값이 너무 크다를 의미하고, 양수라면, 오른쪽 원소의 절대값이 너무 크기 때문에 그에 맞게 두 원소의 idx값을 조절하면 된다.  

---

 

import sys
INF = sys.maxsize

n = int(input())

arr = list(map(int, input().split()))
arr.sort()

start = 0
end = len(arr) - 1

pair = []
min_val = INF
while start < end:
    total = arr[start] + arr[end]
    # 둘 간의 합을 기존과 비교해 작은걸 채택하고, 두 용액의 산성도도 별도 변수에 저장
    if abs(total) < min_val:
        min_val = abs(total)
        pair = (arr[start], arr[end])

    if total >= 0:
        end -= 1
    else:
        start += 1

print(*pair)

---

 

시간 복잡도

포인터가 서로 엇갈려 start 인덱스가 edn 인덱스를 넘어서면 반복문이 멈추게 되어있으므로 시간 복잡도는 O(N)이다.

---

 

 

 

Two pointers algorithm

https://butter-shower.tistory.com/226

[Algorithm] 투포인터(Two Pointer) 알고리즘

https://m.blog.naver.com/kks227/220795165570

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

---