투 포인터(two pointer)

출처 : 한국 코드페어 비타알고 시즌2 투 포인터(two pointer)

1. Two Pointer

---

정렬된 배열에서 두 개의 인덱스를 사용하여 원하는 값을 찾는 기법

---

투 포인터는 정렬된 배열에서 2개의 포인터(인덱스)를 이용하여 두 포인터가 가리키는 값과 찾고자 하는 값(key값)을 비교한 뒤 포인터를 조정하여 원하는 결과를 얻어내는 기법이다. 대표적인 예로 '배열 내 합이 S가 되는 순서쌍 찾기'가 있다.

 

for(int i = 0; i < n; ++i){
    for(int j = i + 1; j < n; ++j){
        if(data[i] + data[j] == S)
            cout << data[i] << '+' << data[j] << '=' << S << endl;
    }
}

위와 같이 간단하게 구현할 수 있지만, 이중 반복문을 이용하면 O(N^2)이 걸린다. 데이터가 커지면 시간 초과가 발생한다. 하지만 투 포인터를 이용하면 정렬되지 않은 배열의 경우 O(NlogN), 정렬된 배열의 경우 O(N) 시간이 걸린다. 

 

2. 원리

위 배열에서 좌측 끝의 포인터를 p, 우측 끝 포인터를 q라 하자. 즉, p는 0번인덱스, q는 12번 인덱스이다.

 

이제 p <= q를 만족하는 동안 다음 작업을 반복한다.

• 두 포인터가 가리키고 있는 원소의 합이 key보다 큰 경우 q를 감소
• 두 포인터가 가리키고 있는 원소의 합이 key보다 작은 경우 p를 증가
• 두 포인터가 가리키고 있는 원소의 합이 key와 같다면 1)p를 증가하고 q를 감소 또는 2)작업 종료

오름차순으로 정렬된 배열의 경우, 원소의 합이 key값 보다 작을 때 오른쪽 인덱스 값을 감소시키면 두 원소의 합이 더 작아지기 때문에 외쪽 인덱스의 값을 증가시켜야 합이 커져서 key값과 가까워진다. 반대의 경우, 합이 key값 보다 클 때는 우측 인덱스를 감소시켜야 합이 작아진다.

 

3. 예시

이제 위의 배열에서 합이 27이 되는 경우를 찾아보자.

p와 q가 가리키는 원소의 합이 29이다. key(27)보다 크다. 따라서 q를 감소시킨다.

 

합이 26으로 key값 27보다 작다. p를 증가시킨다.

합이 28로 27보다 크다. q를 감소시킨다.

 

합이 25로 27보다 작다. p를 증가시킨다.

 

합이 27로 key값과 동일하다. 따라서 순서쌍 하나를 찾은 것이다. 또 다른 순서쌍이 존재할 수 있으므로 계속 반복한다.

이때는 p를 증가하고 q를 감소한다.

 

합이 25, p를 증가한다.

 

합이 28, q를 감소한다.

 

합이 26, p를 증가한다.

 

합이 28, q를 감소한다.

 

합이 27이 되는 또 다른 순서쌍을 찾았다. p를 증가, q를 감소시킨다.

 

이제 두 포인터가 하나의 원소를 가리키고 있고, 이때 원소의 합이 24이므로 찾고자하는 순서쌍이 아니다. 이제 p <= q를 만족하지 않으므로 작업을 종료한다. 

 

4. 코드

1) C++

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, s; cin >> n >> s;
    vector<int> data(n);
    
    for(int i = 0; i < n; ++i)
    	cin >> data[i];
        
    sort(data.begin(), data.end()); # 데이터 오름차순 정렬
    
    int p = 0, q = n-1, cout = 0;
    
    while(p <= q){
    	int sum = data[p] + data[q];
        if(sum > s) --q;
        else if(sum < s) ++p;
        else{
            ++p; --q; ++count
        }
    }
    cout << '합이 ' << s << '와 동일한 순서쌍 개수는 ' << count << '개이다.' << endl;
    return 0;
}

2) Python

import random

# data = [1, 3, 5, 6, 9, 11, 12, 16, 17, 19, 22, 25, 28]
# key = 27
data = list(random.sample(range(1000), 100))
key = sum(data) // len(data)

p = 0; q = len(data)-1; cnt = 0

while p <= q:
    res = data[p] + data[q]
    if res > key : q -= 1
    elif res < key : p += 1
    else :
        p += 1
        q -= 1
        cnt += 1

print(f'합이 {key}가 되는 순서쌍의 개수는 {cnt}이다.')