(JavaScript) 투 포인터의 개념 정리

투 포인터를 사용해야 하는 문제는 모든 경우의 수를 확인하는 방법(브루트포스)을 사용하면 시간초과가 발생한다. 특정 범위 혹은 특정한 두 값에 대해 문제에서 주어진 조건과 매치를 하는 경우 투 포인터 기법을 활용하여 수행 시간(시간복잡도)을 단축시킬 수 있다.

 

 

1. 투포인터란?

투 포인터 알고리즘은 배열 혹은 리스트를 순회하면서 두 개의 포인터를 사용해 문제를 해결하는 기법이다.

주로 연속적인 구간을 찾거나, 특정 조건을 만족하는 두 요소를 탐색할때 사용된다.

 

1. 두 개의 포인터 활용
   배열에서 두개의 포인터를 가지고 특정 조건을 탐색한다. 두 포인터를 합하는 등 단순히 활용할수도 있으며 두 포인터 사이값을 활용하여 특정 조건에 맞는지 검사할 수 도 있다.
2. 정렬된 배열에서 주로 사용
   투 포인터는 좌우 포인터를 이동시키며 특정 조건을 찾는다. 이때 자연스럽게 수를 증감시키기위해서 정렬된 배열이 필요하다.
3. 실행 시간 단축 (시간복잡도 최적화)
   배열에서 조건을 만족하는 두 수를 찾기위해서는 일반적으로 배열을 두번 순회하는것과 같은 시간 (O(N^2))이 걸리지만 포인터로 해결하면 시간을 단축시킬 수 있다.

 

 

2. 투포인터의 유형

2-1. 두 요소의 합

배열에서 두 수의 합이 특정 값이 되는 경우를 찾을때 사용할 수 있다.

 

• 두 요소 합 기본 접근방법

1. 주어진 배열 정렬
   먼저 배열을 정렬한다. 두 값을 차근차근 변화시켜 목표값을 찾아야하기 때문이다.
2. 초기 포인터 위치 지정
   왼쪽 포인터는 0 에서, 오른쪽 포인터는 배열길이 - 1 에서 시작한다. (좌측끝, 우측끝)
3. 두 수의 합이 목표값보다 클경우 오른쪽 포인터 이동
   두 수의 합이 목표값보다 크면 오른쪽 포인터를 왼쪽으로 한 칸 이동한다. (두 수의 합 감소)
4. 두 수의 합이 목표값보다 작을경우 왼쪽 포인터 이동
   두 수의 합이 목표값보다 작으면 왼쪽 포인터를 오른쪽으로 한 칸 이동한다. (두 수의 합 증가)
5. 3~5의 과정을 반복
   목표값을 찾을때까지 반복한다. 목표값에 맞는 두 수를 찾으면 해당 수를 반환하고 반복을 종료한다.

 

아래는 배열 내 항목중 두 수를 합쳐서 목표값을 만들 수 있는지 검사하는 예제이다.

function twoSum(numbers, target) {
    numbers.sort((a, b) => a - b);

    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        let sum = numbers[left] + numbers[right];
        if (sum === target) return [numbers[left], numbers[right]];
        else if (sum < target) left++;
        else right--;
    }
    return [];
}

console.log(twoSum([1, 7, 4, 2, 15, 11], 9)); // [2, 7]

 

• 코드 실행 과정

1. 주어진 배열은 [1, 2, 4, 7, 11, 15] 순서로 정렬된다. 목표값은 9이다.
2. 포인터의 초기 위치를 지정한다. 왼쪽 포인터는 1 이고 오른쪽 포인터는 15이다.
3. 두수를 합해 비교하는 과정을 반복한다. 두 포인터가 만나거나 교차하면 안되므로 left < right 조건을 활용한다.
4. 첫번째 두 수의 합은 16(1+15)이다. 목표값보다 크므로 오른쪽 포인터가 이동하여 11을 가리킨다.
5. 두번째 두 수의 합은 12(1+11)이다. 목표값보다 크므로 오른쪽 포인터가 이동하여 7을 가리킨다.
6. 세번째 두 수의 합은 8(1+7)이다. 목표값보다 작으므로 왼쪽 포인터가 이동하여 2를 가리킨다.
7. 네번째 두 수의 합은 9(2+7)이다. 목표값이므로 현재 포인터가 가리키는 [2, 7]을 반환한다.

 

 

 

2-2. 특정 구간의 합 (슬라이딩 윈도우)

배열에서 특정 구간의 합을 구할때 투 포인터를 활용할 수 있다. 두 수를 기준으로 잡고 사이 값을 활용한다.

이때 두 수의 간격을 유지하며 포인터를 이동시키면 슬라이딩 윈도우 기법이 된다.

 

• 특정 구간 합 기본 접근방법

1. 초기 포인터 위치 지정
   두 포인터가 0에서 출발한다. 간격을 조정하며 구간합을 구한다. (둘다 좌측끝)
2. 오른쪽 포인터를 증가시키면서 구간합을 누적
   목표값과 같거나 클때까지 오른쪽 포인터를 증가시키며 구간합을 누적한다.
3. 목표값보다 커질경우 왼쪽 포인터를 증가시키면서 구간합을 감소
   왼쪽 포인터가 이동하면 구간이 짧아지므로 (왼쪽값이 하나씩 없어지므로) 값이 감소한다.
4. 합이 목표값과 같으면 반환 혹은 활용
   목표값을 찾을때까지 반복한다. 찾을경우 반환하고 종료하거나 적절히 활용한다.

여기서는 주어진 배열에서 특정 구간의 합을 구해야 하므로 정렬은 하지않는다.

 

 

아래는 배열 내 특정 구간의 합이 목표값인것 중 그 길이가 가장 짧은 구간의 길이를 구하는 예제이다.

function minSubArrayLen(target, nums) {
    let left = 0,
        sum = 0,
        minLength = Infinity;

    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];

        while (sum >= target) {
            if (sum === target) minLength = Math.min(minLength, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }

    return minLength === Infinity ? 0 : minLength;
}

console.log(minSubArrayLen(7, [1, 3, 2, 1, 4, 2, 5])); // 출력: 2 ([2, 5])

 

• 코드 실행 과정

1. 초기 포인터는 좌우측 포인터 둘다 0을 가리킨다.
2. 우측 포인터를 먼저 증가시키면서 구간합을 누적한다.
3. 구간합이 목표값보다 높을경우 왼쪽 포인터를 이동시켜 구간합을 감소시킨다.
4. 구간합이 목표값과 같을경우 minLength값을 갱신한다. 기존 minLength값보다 작은 경우만 갱신된다.
5. 반복이 종료되고 가장 짧은 구간합의 길이인 minLength를 반환한다.

 

 

※ 부분합을 활용한 구간합 구하기 vs 투포인터를 활용한 구간합 구하기

구간합은 투포인터를 이용한 방식 외에도 부분합을 활용해서 구할 수 있다. 두 기법은 상황에 맞춰 사용해야 한다.

1. 부분합을 활용한 구간합 구하기 (DP의 Bottom-up)
   •    미리 부분합을 구해두고 부분합 끼리의 차이를 활용해 구간합을 구할 수 있다.
   •    구간합을 여러번 구해야할때 유용하다. 부분합을 저장해둔 배열을 통해 O(1)의 시간복잡도로 구간합을 구할 수 있다.
   •    시간복잡도는 O(N) + O(1) 이다. (부분합 배열 계산 + 구간합 구하기)
2. 투포인터를 활용한 구간합 구하기
   •    포인터를 이동하며 조건에 맞는 구간이 존재하는지 검사한다.
   •    가변 길이의 부분 배열을 찾거나 한번의 탐색으로 최적해를 구할때 유용하다.
   •    시간복잡도는 O(N)이다. (한번의 순회로 구간합 찾기)

 

 

3. 결론

글에서 작성한 예제는 매우 간단한 예시이고 실제 투 포인터는 훨씬 복잡하게 사용된다.

그럼에도 투 포인터가 유리한 상황에서는 확실한 실행시간의 이득을 가져다주므로 유형과 사용법을 익혀 둘 필요가 있다.

여러 문제를 풀어보며 투포인터 활용 자체에 익숙해지는것이 문제풀이에 큰 도움이 된다.