19. 투 포인터

투 포인터

빠른 설명

투 포인터는 두 개의 인덱스를 움직이며 배열이나 문자열을 한 번에 훑는 기법이다. 정렬된 배열에서 쌍을 찾거나, 구간을 유지하며 조건을 확인할 때 자주 쓴다.

언제 쓰는가

• 정렬된 배열에서 두 수의 합 찾기
• 양끝에서 가운데로 좁혀 가는 문제
• 같은 방향으로 움직이며 구간을 관리하는 문제

시간복잡도

• 보통 $O(N)$
• 정렬이 먼저 필요하면 전체 $O(N\log N)$

참고자료

• USACO Guide - Two Pointers
• GeeksforGeeks - Two Pointer Technique
• Codeforces EDU - Two Pointers Method

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    vector<int> a = {1, 2, 4, 7, 11};
    int target = 9;
 
    int left = 0, right = (int)a.size() - 1;
    while (left < right) {
        int sum = a[left] + a[right];
        if (sum == target) {
            cout << left << ' ' << right << '\n';
            break;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
}

Python 코드

a = [1, 2, 4, 7, 11]
target = 9
 
left, right = 0, len(a) - 1
while left < right:
    s = a[left] + a[right]
    if s == target:
        print(left, right)
        break
    elif s < target:
        left += 1
    else:
        right -= 1