투 포인터

정렬된 배열(또는 리스트)에서 두 개의 인덱스를 양 끝 또는 한쪽 끝에서 시작해 조건에 따라 이동시키며 선형 시간에 답을 찾는 기법입니다.

동작 과정

문제: 정렬된 배열에서 합이 target인 두 수 찾기

A = [1, 3, 5, 7, 9, 11]   target = 14

left=0, right=5  (A[0]=1, A[5]=11)  sum=12 < 14  → left++
left=1, right=5  (A[1]=3, A[5]=11)  sum=14 = 14  → 발견! (3, 11)

sum이 target보다 작다  → left를 오른쪽으로 옮겨 sum을 키운다
sum이 target보다 크다  → right를 왼쪽으로 옮겨 sum을 줄인다
sum이 target과 같다   → 정답, 필요하면 left++, right-- 로 다음 쌍도 탐색

배열이 정렬되어 있기 때문에 left를 옮기면 sum이 커지고 right를 옮기면 sum이 작아진다는 단조성이 보장되어, 모든 (left, right) 쌍을 확인하는 O(N²) 대신 각 인덱스를 한 번씩만 이동해 O(N)에 끝낼 수 있습니다.

구현

int[] twoSumSorted(int[] a, int target) {
    int left = 0, right = a.length - 1;

    while (left < right) {
        int sum = a[left] + a[right];
        if (sum == target) {
            return new int[] { left, right };
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[] { -1, -1 };
}

// 응용: 세 수의 합이 target인 조합 찾기 (하나를 고정하고 나머지에 투 포인터)
boolean threeSumSorted(int[] a, int target) {
    for (int i = 0; i < a.length - 2; i++) {
        int left = i + 1, right = a.length - 1;
        while (left < right) {
            int sum = a[i] + a[left] + a[right];
            if (sum == target) return true;
            else if (sum < target) left++;
            else right--;
        }
    }
    return false;
}

복잡도

입력이 정렬되어 있지 않다면 정렬에 O(N log N)이 먼저 필요합니다. 세 수의 합처럼 하나를 고정하고 나머지에 투 포인터를 적용하는 패턴은 전체 시간복잡도가 O(N²)이 됩니다.

주의사항

• 정렬 전제: 단조성이 투 포인터 이동의 정당성을 보장하므로, 정렬되지 않은 입력에 그대로 적용하면 틀린 답을 낸다
• left < right 대신 left <= right를 쓰면 같은 원소를 두 번 쓰는 경우가 생길 수 있다. 문제에서 같은 인덱스 재사용을 허용하는지 먼저 확인한다
• 중복 값 처리: 같은 값이 여러 번 나오는 배열에서 중복 쌍을 제거해야 한다면, 쌍을 찾은 뒤 left/right를 중복 값만큼 추가로 건너뛰어야 한다
• 두 인덱스가 서로를 향해 좁혀 들어가는지(two sum 유형), 아니면 같은 방향으로 창을 유지하는지(슬라이딩 윈도우 유형)를 구분해야 한다 — 전자는 양 끝에서 시작해 좁혀가고, 후자는 한쪽 끝에서 같은 방향으로 이동한다

핵심 정리

• 정렬된 자료에서 두 인덱스를 조건에 따라 이동시켜 O(N)에 답을 찾는 기법
• 핵심 조건은 단조성: 한 포인터를 옮기면 비교 대상 값이 단조적으로 변해야 한다
• 세 수의 합처럼 하나를 고정하고 나머지에 적용하는 식으로 확장할 수 있다
• 양 끝에서 좁혀가는 방식이며, 창을 유지하며 같은 방향으로 이동하는 슬라이딩 윈도우와는 구분된다