[알고리즘] 다중 포인터 패턴 (Multiple Pointers)

다중 포인터(Multiple Pointers) 패턴이란?

다중 포인터(Multiple Pointers) 패턴은 인덱스나 위치에 해당하는 포인터(or 값)를 만든 다음, 특정 조건에 따라 중간 지점에서부터 시작 지점-끝 지점 또는 양쪽 지점을 향해 이동시키는 패턴이다.

한 쌍의 값이나 조건을 충족시키는 해답을 찾을 때 주로 사용된다.

 

🔍 예시 문제

차례대로 정렬된 숫자 배열이 존재할 때, 두 수끼리 더했을 때 0이 나오는 쌍의 개수를 구하라. 

sumZero([-4,-3,-2,-1,0,1,2,5]) // 2 (-2,2 / -1,1)

다중 포인터 패턴을 적용하지 않았을 때 O(n²)

function sumZero(arr){
    for(let i = 0; i < arr.length; i++){
        for(let j = i+1; j < arr.length; j++){
            if(arr[i] + arr[j] === 0){
                return [arr[i], arr[j]];
            }
        }
    }
}

• 시간 복잡도 : O(N^2) 모든 가능한 쌍을 확인한다.

 

다중 포인터 패턴을 적용했을 때 O(n)

function sumZero(arr){
    let left = 0; 
    let right = arr.length - 1;
    while(left < right){
        let sum = arr[left] + arr[right];
        if(sum === 0){
            return [arr[left], arr[right]];
        } else if(sum > 0){
            right--;
        }else{
            left++;
        }
    }
}

• 시간복잡도: O(n) - 각 요소를 최대 한 번만 확인한다. 

🎯 다중포인터 패턴 비교

🔍 방법 1: 중첩 루프

시간복잡도: O(n²) | 공간복잡도: O(1)

준비됨

⚡ 방법 2: 다중포인터 패턴

시간복잡도: O(n) | 공간복잡도: O(1)

준비됨