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

투 포인터 기법이란?

• 2개의 포인터를 만들어서 각각이 가리키는 원소에 의미를 부여하여 요구하는 문제를 해결하는 알고리즘
• O(N^2)를 O(N)으로 줄일 수 있다.
• 대다수는 정렬된 배열에서 사용한다. 정렬된 배열에서 O(N^2) 탐색 중 필요 없는 연산을 버려서 O(N)으로 줄인다.
• 포인터에 의미를 부여하는 작업에 대한 예시들을 다양하게 접해야 한다.

투 포인터 대표 유형

1. 포인터 2개가 양끝에서 반대로 진행해 나아가는 방식
2. 포인터 2개가 같은 방향으로 진행해 나아가는 방식
3. 포인터 하나는 한쪽 방향으로만 진행하고, 다른 포인터는 양쪽으로 이동하는 것

투 포인터 동작 원리

10개의 서로 다른 양의 정수로 정렬된 수열에서, 두 수 (i, j)의 합이 13을 만족하는 경우의 수를 구하시오. (1 ≤ i < j ≤ n = 10)

만약 위 문제를 완전 탐색으로 풀 경우, 코드는 다음과 같다. 이 때의 시간 복잡도는 O(N^2)이다.

int answer = 0;

for (int i = 0; i < 10; i++) {
	for (int j = i + 1; j < 10; j++) {
		if (arr[i] + arr[j] == 13) answer++;
	}
}

var answer = 0

for i in 0..<10 {
	for j in i..<10 {
		if (arr[i] + arr[j] == 13) {
			answer += 1
		}
	}
}

 

 

먼저 완전 탐색을 진행해보면,

 

인덱스 i = 3, j = 5일 때 arr[3] + arr[5] = 13이므로 answer을 1 증가시킨다.

 

 

 

이제 j가 1 증가하는데, arr[3] + arr[6] = 14 > 13이기 때문에, 이후 진행되는 j의 증가 연산은 모두 의미가 없어진다.

또한 여기서 i의 값을 1 증가시키면 arr[4] + arr[6] = 15 > 13이므로, 이후 진행되는 i의 증가 연산 또한 의미가 없어진다.

즉, arr[i] + arr[j] > 13이라면 i와 j를 더 이상 증가시킬 필요가 없다.

 

이제 투포인터 유형을 살펴보자!

 

 

포인터 2개가 양끝에서 반대로 진행해 나아가는 방식

leftPointer는 가장 왼쪽 끝을, rightPointer는 가장 오른쪽 끝을 가리키도록 하자.

 

1. leftPointer의 인덱스 = 0, rightPointer의 인덱스 = 9

arr[0] + arr[9] = 18 > 13이므로, 두 합을 감소시켜야 하는 상황이다.

두 합을 감소시켜야 하는 상황에서는 rightPointer를 감소시킨다.

왜냐? 두 합은 13보다 크다.

배열은 오름차순으로 정렬되어있고, leftPointer를 증가시키는 것은 두 합을 감소시키는 것이 아니라 증가시키는 셈이 된다.

그래서 leftPointer를 증가시키는 것이 아닌, rightPointer를 감소시키는 것이다.

 

즉, 주어진 배열은 오름차순이기 때문에 arr[leftPointer] + arr[rightPointer] = 13을 만족시키는 rightPointer에 해당하는 원소는 줄어든다.

따라서 leftPointer = 0일 때, 어떤 k가 arr[0] + arr[k] > 13이라면 이후의 k+1, k+2, ..의 인덱스를 갖는 배열의 원소는 탐색할 필요가 없다.

 

 

2. leftPointer의 인덱스 = 0, rightPointer의 인덱스 = 8

arr[0] + arr[8] = 17 > 13이므로, 이번에도 두 합을 감소시켜야 하는 상황이다.

앞에서와 마찬가지로 rightPointer를 감소시킨다.

 

 

3. leftPointer의 인덱스 = 0, rightPointer의 인덱스 = 7

arr[0] + arr[7] = 15 > 13으로, 이번에도 두 합을 감소시켜야 하는 상황이다.

앞에서와 마찬가지로 rightPointer를 감소시킨다.

 

4. leftPointer의 인덱스 = 0, rightPointer의 인덱스 = 6

arr[0] + arr[6] = 10 < 13이므로, 이번에는 두 합을 증가시켜야 하는 상황이다.

이번에는 leftPointer를 증가시킨다.

 

 

5. leftPointer의 인덱스 = 1, rightPointer의 인덱스 = 6

arr[1] + arr[6] = 11 < 13이므로, 두 합을 증가시켜야 하는 상황이다.

leftPointer를 증가시킨다.

 

 

6. leftPointer의 인덱스 = 2, rightPointer의 인덱스 = 6

arr[2] + arr[6] = 12 < 13이므로, 두 합을 증가시켜야 하는 상황이다.

leftPointer를 증가시킨다.

 

 

7. leftPointer의 인덱스 = 3, rightPointer의 인덱스 = 6

arr[3] + arr[6] = 14 > 13이므로, 두 합을 감소시켜야 하는 상황이다.

rightPointer를 감소시킨다.

 

 

8. leftPointer의 인덱스 = 3, rightPointer의 인덱스 = 5

arr[3] + arr[5] = 13이므로, 정답이다.

이번에는 leftPointer를 증가시켜도 되고, rightPointer를 감소시켜도 된다.

leftPointer를 증가시켜보자.

 

 

9. leftPointer의 인덱스 = 4, rightPointer의 인덱스 = 5

arr[4] + arr[5] = 14 > 13이므로, 두 합을 감소시켜야 하는 상황이다.

이 때 rightPointer를 감소시키면 arr[4] + arr[4] = 6 + 6 = 12이므로, leftPointer를 증가시킨다.

 

 

10. leftPointer의 인덱스 == rightPointer의 인덱스 == 5

두 포인터의 인덱스가 같다. 이제 두 수의 조건이 i < j이므로 탐색 과정을 종료한다.

 

 

포인터 2개가 같은 방향으로 진행해 나아가는 방식

빠른 포인터가 느린 포인터보다 앞서는 방식으로, 빠른 포인터 (rightPointer)는 항상 느린 포인터 (leftPointer)보다 앞서 있다.

느린 포인터 (leftPointer)는 빠른 포인터 (rightPointer)를 역전해서는 안된다.

자세한 설명은 이 문제를 참고하면 된다.

 

투 포인터 코드

int leftPointer = 0;
int rightPointer = n - 1;
int answer = 0;

while (leftPointer < rightPointer) {
	int sum = arr[leftPointer] + arr[rightPointer];
	if (sum > 13) rightPointer--;
	else if (sum < 13) leftPointer++;
	else {
		answer++;
		rightPointer--; // leftPointer++; 해도 괜찮다!
	}
}

var leftPointer = 0;
var rightPointer = n - 1;
var answer = 0;

while (leftPointer < rightPointer) {
	var sum = arr[leftPointer] + arr[rightPointer];
	if (sum > 13) {
		rightPointer -= 1
	}
	else if (sum < 13) {
		leftPointer += 1
	} else {
		answer += 1
		rightPointer -= 1 // leftPointer += 1 해도 괜찮다!
	}
}

leftPointer, rightPointer가 양쪽에서 다가오고, 중간에 두 포인터가 만나면 탐색을 종료하므로 leftPointer, rightPointer가 움직인 거리 == 총 배열의 길이이다. 따라서 시간 복잡도는 O(N)이다.