투 포인터 (Two Pointers)

투 포인터 (Two Pointers)

투 포인터 알고리즘은 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻어내는 알고리즘입니다.

🎈 예제

길이가 n인 1차원 배열이 있을 때, 그 부분 배열의 원소의 합이 m이 되는 경우의 수를 알고 싶습니다.
모든 부분 배열을 탐색한다면 시간복잡도는 O(n^2)이 되겠습니다.
그러나 투 포인터를 사용하면 O(n) 에 문제를 해결할 수 있습니다.

• 포인터 2개를 만듭니다. start, end라고 하겠습니다.
• 처음 시작할 때는 start, end = 0 입니다.
• start <= end는 항상 성립합니다.

투 포인터의 동작 과정은 이렇습니다.
start < n인 동안 반복

1. 현재 부분합이 m 이상이거나 end == n인 경우
   start를 오른쪽으로 한 칸 이동
2. 그렇지 않다면 end를 오른쪽으로 한 칸 이동
3. 현재 부분합이 m이라면 결과 count++

🎈 Java 코드

int start = 0;
int end = 0;
int result = 0; 
int sum = 0;

while (start < end) {
    if (sum >= m) {
        start++; // start를 오른쪽으로 옮김
        sum -= arr[start];
    }
    else if (end == n) {
        break;
    }
    else {
        end++; // end를 오른쪽으로 옮김
        sum += arr[end];
    }

    if (sum == m) {
        result++;
    }
}

🎈 그림으로 보는 예제

그림으로 보면 위와 같을 것입니다 ^_^