[Algorithm] Two Pointer 투 포인터

Two Pointer Algorithm

---

투 포인터 알고리즘은 연속되는 1차원 배열 또는 리스트를 순차적으로 접근할때 사용하는 알고리즘이다. 이름 그대로 시작점과 끝점을 가리키는 두 개의 포인터를 이용하여 부분배열을 탐색한다. 투 포인터 알고리즘을 사용하는 이유는 당연히 배열 탐색시 시간복잡도에서의 효율을 위해서이다.

 

예를 들어, 길이가 100인 배열(0 포함)에서 합이 15가되는 부분배열 중 길이가 가장 짧은 배열을 찾아야한다고 해보자. 첫번째 원소부터 차례대로 탐색한다면 99번 원소에 15가 있다고 할때 최악의 경우로 약 O(n^2/2)의 시간복잡도를 가질 것이다. 투 포인터 알고리즘의 예제와 투 포인터 알고리즘을 사용한다면 시간복잡도가 어떻게 나오는지 살펴보자. 아래는 투 포인터 알고리즘을 적용할 수 있는 문제와 해결 코드이다.

 

프로그래머스 레벨2 연속된 부분 수열의 합

프로그래머스

class Solution {
    public int[] solution(int[] sequence, int k) {
        int sIdx = 0;
        int eIdx = sequence.length;

        int sum = 0;
        for(int left=0, right=0; left<sequence.length; left++) {
            //조건을 만족할때까지 right pointer 조정
            while(sum < k && right < sequence.length) sum += sequence[right++];

            if(sum == k) {
                if((eIdx-sIdx) > right-left) {
                    sIdx = left;
                    eIdx = right;
                }
            }

            sum -= sequence[left];
        }

        int[] answer = {sIdx, eIdx-1};
        return answer;
    }
}

 

위 코드의 핵심 로직인 for문 내부를 보면 조건에 맞게 left와 right를 조정해주면서 기존 sequence배열을 기반으로 반복해서 부분배열을 만들어내며 해를 찾아내는것을 볼 수 있다. 위 문제의 최악의 경우 시작복잡도는 O(2n)이다. 앞서 다뤘던 얘기 또한 해당 문제와 같은 내용이기때문에 O(n^2/2)와 O(2n) 둘을 비교했을때 시간적으로 많은 차이가 난다.

 

개념을 이해하면 생각보다 쉽고 단순한 알고리즘이기 때문에 설명은 이 정도로 충분한 것 같고, 투 포인터 알고리즘에 대해 배열과 포인터를 시각적으로 표현한 예제를 보고 싶으면 아래 포스트를 참고하면 좋을 것 같다.

 

[Java]투 포인터 / 슬라이딩 윈도우 알고리즘