두 용액 ( 2470 번 )

2470번: 두 용액

 

---

🧠 알고리즘

• 투 포인터 (Two Pointer)

 

✔️ 동작 방식

• 용액 리스트를 오름차순으로 정렬한다.
• 왼쪽 포인터 l은 가장 작은 값부터, 오른쪽 포인터 r은 가장 큰 값부터 시작한다.
• 두 용액의 합 sum_value = n_list[l] + n_list[r]을 계산한다.
  • 합의 절댓값이 현재 최소값(score)보다 작으면, 결과(answer)를 갱신한다.
• 합이 0보다 크면 → 용액의 합을 줄이기 위해 오른쪽 포인터 r을 왼쪽으로 이동한다.
  합이 0보다 작으면 → 합을 키우기 위해 왼쪽 포인터 l을 오른쪽으로 이동한다.
• 두 포인터가 만나기 전(l < r)까지 반복한다.
• 최종적으로 0에 가장 가까운 두 용액의 특성값을 반환한다.

---

 

🧾 코드

import sys

def _main(n, n_list):
    answer = []
    score = 2000000001
    l, r = 0, n-1
    n_list.sort()

    while l < r:
        l_value, r_value = n_list[l], n_list[r]
        sum_value = l_value + r_value
        abs_value = abs(sum_value)
        
        if abs_value < score:
            answer = [l_value, r_value]
            score = abs_value

        if sum_value > 0:
            r -= 1
        else:
            l += 1

    return ' '.join(map(str, answer))


n = int(sys.stdin.readline().rstrip())
n_list = list(map(int, sys.stdin.readline().rstrip().split()))

print(_main(n, n_list))

---

 

⏱️ 시간 복잡도

n_list.sort() : 정렬 알고리즘 ( 선형 로그 시간 복잡도 )
while l < r : 투 포인터 탐색 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )