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

1차원 배열이 주어졌을 때, 특정 연속된 구간의 합이 M이 되는 경우의 수를 구하려면 어떻게 해야 할까?

가장 단순하게 생각해볼 수 있는 방법은 2중 반복문을 돌리는 것이다.

public class Main {
 
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2}; // 크기가 10인 1차원 배열 
        int m = 5; // 연속된 구간의 합이 5인 경우를 찾는다.
        
        int count = 0;
        for (int i = 0; i < 10; i++) {
            int sum = arr[i];
            
            for (int j = i + 1; j < 10; j++) {
                if (sum == m) {
                    count++;
                } else if (sum > m) {
                    break;
                } else {
                    sum += arr[j];
                }
            }
        }
    }
}

 

당연히 위의 방법과 같이 이중 반복문을 돌리게 되면 시간 복잡도가 $\mathcal{O}(N^2)$ 으로 배열의 크기가 커지면 커질수록 느려진다.

1차원 배열의 연속된 구간에 대해 2중 반복문을 개선하기 위해 나온 것이 투 포인터 알고리즘이다.

 

 

 

투 포인터(Two Pointers) 알고리즘

---

아래와 같은 1차원 배열이 있다.

[그림 1] 예시 1차원 배열

 

위의 1차원 배열에 대해 연속된 구간의 합이 5인 것의 경우의 수를 구해보자.

위의 2중 반복문과 큰 차이는 없는데, Right를 우측으로 하나씩 옮기면서 arr[left] + ... + arr[right]의 값이 5보다 크다면 더이상 right를 우측으로 옮기는건 무의미하다. right를 우측으로 옮겨봤자 마찬가지로 5보다 크기 때문이다. 따라서, 이 경우 left를 우측으로 옮긴다.

 

코드로 살펴보자.

public class Main {
 
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2}; // 크기가 10인 1차원 배열 
        int m = 5; // 연속된 구간의 합이 5인 경우를 찾는다.
        
        int count = twoPointers(arr, m);
    }
    
    private static int twoPointers(int[] arr, int m) {
        int sum = 0, count = 0;
        int left = 0, right = 0;
        
        while (true) {
            if (sum > m) { // 1. left를 우측으로 옮기는 경우 
                sum -= arr[left++];
            } else if (right == arr.length - 1) { // right를 우측으로 옮기기 전에 배열의 끝을 가리키는지 확인한다.
                break;
            } else { // 2. right를 우측으로 옮기는 경우 
                sum += arr[right++];
            }
            
            if (sum == m) count++;
        }
        
        return count;
    }
}