백준 2470: 두 용액 (골드 V) - 투포인터

기업 코딩테스트의 마지막 문제에서 투포인터 문제가 나왔었는데, 종료조건을 건드리다가 시간을 넘겨버렸다. 투포인터의 개념을 이론적으로 알고는 있었지만 실제 투포인터 문제를 풀어본 적은 거의 없다. 이 참에 공부해보자.

2470번: 두 용액

 

문제요약

주어진 리스트에서  두 원소의 합이 0과 가장 가까운 원소를 찾는것이다. 원소의 범위는 -10억 ~ 10억 이며, 원소의 개수는 최대 10만개 이므로 모든 경우를 탐색하는 O(N^2)으로 풀어낼 수 없다. 이 때 투 포인터를 사용한다.

예를 들어 [-2, 4, -99, -1, 98] 이 주어졌을 때, 0과 가장 가까운 조합은 -99와 98이다.

솔루션

1. 리스트를 정렬한다.

2. 포인터 두 개를 준비한다. left_pointer는 0으로, right_pointer는 N-1로 두어 양쪽에서 탐색을 시작한다.

3. 두 원소의 합이 0보다 크면, right_pointer를 왼쪽으로 한 칸 이동시키고 (값이 작아짐)

4. 두 원소의 합이 0보다 작다면, left_pointer를 오른쪽으로 한 칸 이동시킨다. (값이 커짐)

5. 중간에 두 원소의 합이 0이라면 조기중단한다. (최소이므로)

6. left와 right pointer가 만나기 전까지 반복한다.

뭔가 이분탐색은 아니지만 느낌은 비슷하다. 이로서 O(N)의 알고리즘으로 원하는 조합을 탐색할 수 있다.

 

코드, 복붙은 하지 말자!

import sys
input = sys.stdin.readline
N = int(input())

nums = list(map(int, input().split()))
nums.sort()
p1 = 0
p2 = N-1
result = [nums[p1], nums[p2]]
answer = abs(nums[p1] + nums[p2])
while p1 < p2:
    left = nums[p1]
    right = nums[p2]
    
    sum_num = left + right
    
    if abs(sum_num) < answer:
        answer = abs(sum_num)
        result = [left, right]
        if answer == 0:
            break

    if sum_num < 0:
        p1 += 1
        
    else:
        p2 -= 1
        
print(result[0], result[1])