투 포인터 (Two Pointer)

투 포인터란?

정렬된 리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 타겟 값과 같을 때 까지 포인터를 조작하는 기법을 말한다. 두 개의 포인터를 함께 활용할 때 얻을 수 있는 이점은 무엇일까? 투 포인터를 활용한 대표적인 예로 아래와 같은 문제가 있다.

Q. 정렬된 리스트 A와 타겟 값 S가 주어졌을 때, 두 수의 합이 S가 되는 순서쌍을 모두 구하여라.
> A = [1, 3, 5, 6, 9, 11, 12, 16, 17, 19, 22, 25, 28]
> S = 27 

1. 이중 반복문을 이용한 풀이

가장 먼저 떠오르는 풀이는 이중 반복문을 이용해 모든 쌍을 탐색하며 조건을 만족하는 경우를 찾는 방법이다.

A = [1, 3, 5, 6, 9, 11, 12, 16, 17, 19, 22, 25, 28]
S = 27 

for i in range(len(A)):
    for j in range(i+1, len(A)):
        if A[i] + A[j] == S:
            print(f'{A[i]} + {A[j]} = {S}')   

매우 단순하며 직관적이다. 하지만 치명적인 문제가 있으니.. 이중 반복문을 이용하는 경우 시간 복잡도는 $O(n^2)$이기 때문에 리스트의 데이터가 커지면 시간초과가 발생할 가능성이 다분하다. 여기서 투 포인터의 위력이 드러난다.

2. 투 포인터를 이용한 풀이

투 포인터를 알고리즘은 다음과 같다.

1. 리스트를 오름차순으로 정렬한다.
2. 포인터 left는 리스트의 시작점을, 포인터 right는 리스트의 끝점을 가리킨다.
3. left와 right가 만날 때 까지(즉, 모든 경우를 확인할 때 까지) 다음을 반복한다.
   3-1. A[left]와 A[right]의 합이 타겟 값(S)과 같다면 조건을 만족하므로 출력하고, left를 1 증가, right를 1 감소시킨다.
   3-2. A[left]와 A[right]의 합이 타겟 값(S)보다 작다면 left를 1 증가시킨다.
   3-3. A[left]와 A[right]의 합이 타겟 값(S)보다 크다면 right를 1 감소시킨다.

이 알고리즘을 그대로 코드로 나타내보자.

A = [1, 3, 5, 6, 9, 11, 12, 16, 17, 19, 22, 25, 28]
S = 27 

# A.sort()  # 이미 정렬된 경우에는 필요 없음
left, right = 0, len(A)-1
while left <= right:
    tmp = A[left] + A[right]
    if tmp > S: 
        right -= 1
    elif tmp < S:  
        left += 1
    else: 
    	# 조건 만족
        print(f'{A[left]} + {A[right]} = {S}')
        left += 1
        right -= 1

투 포인터를 활용하면 리스트를 한 번만 탐색하기 때문에, 리스트가 이미 정렬되어 있는 경우 $O(n)$, 정렬되어 있지 않더라도 $O(nlogn)$ 정도의 시간 복잡도로 문제를 해결할 수 있다.

사소한 아이디어 같지만 데이터가 커질수록 투 포인터의 위력은 어마어마해진다. 주어진 문제의 입력 데이터가 클 경우, 투 포인터를 활용할 수 있을지 꼭 한 번씩 생각해보도록 하자!