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

아래 강의를 듣고 내용을 정리한 포스트 입니다.

https://www.udemy.com/course/best-javascript-data-structures/

JavaScript (JS) Algorithms and Data Structures Masterclass

 

다중 포인터 패턴이라는 이름은 공식적인 이름은 아닙니다. 개념적으로는 한 쌍의 값이나 조건을 충족시키는 무언가를 찾는다는 개념입니다.

오름차순으로 정렬된 리스트에서 한 쌍의 값이나 조건을 충족시키는 무언가를 찾을 때 사용할 수 있는 이 방법은 시간 복잡도가 O(n)으로 매우 효율적입니다.

언제 사용하는가 ?

- 배열, 문자열 ( 오름차순 정렬 )
- 조건에 맞는 한쌍의 값 찾기 등 무언가를 찾을 때
- 로직에 따라 한번에 한 포인터만 이동할수도 있고, 두 포인터가 같이 움직일수도 있다.

필요 조건 : 오름차순의 정렬된 배열, 문자열
핵심 : 두 포인터를 특정 조건에 따라 중간 지점에서부터 특정 방향으로 이동시킴.

이제는 예제를 통해서 이 방법을 활용하는 코드를 작성해볼 것입니다. 아래 예제를 살펴보겠습니다.

예제 1

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

위 코드는 입력된 배열에서 더해서 0이 되는 두 수를 찾는 문제입니다. 만약 이 문제를 two pointer 패턴을 활용해서 푼다면, 포인터 두 개를 생성하고, 배열의 가운데부터 시작하여 끝까지 이동하면서 값을 검색하는 방법을 사용할 수 있습니다. 이 방법을 활용한 코드는 다음과 같이 작성할 수 있습니다.

const sumZero = (arr: number[]) => {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const sum = arr[left] + arr[right];

    if (sum === 0) {
      return [arr[left], arr[right]];
    } else if (sum > 0) {
      right--;
    } else {
      left++;
    }
  }
}

주어진 배열에서 포인터를 생성하고, 포인터를 중간으로 이동시키면서 값을 검색합니다. 만약 합이 0이라면 해당 값을 반환하고, 합이 0보다 크다면 오른쪽 포인터를 왼쪽으로 이동시키고, 합이 0보다 작다면 왼쪽 포인터를 오른쪽으로 이동시킵니다.

예제 2

countUniqueValues([1, 1, 1, 1, 1, 2]); // 2
countUniqueValues([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]) // 7
countUniqueValues([]) // 0
countUniqueValues([-2, -1, -1, 0, 1]) // 4

위 코드는 주어진 배열에서 중복을 제거한 원소의 개수를 반환하는 문제입니다. 이 함수도 two pointer 패턴을 사용하여 구현할 수 있습니다.

이번에는 가운데부터 시작하지 않고, 주어진 배열에 중복되지 않는 값을 할당해가면서 찾는 방식으로 구현할 수 있습니다.

const countUniqueValues = (arr: number[]) => {
  if (arr.length === 0) {
    return 0;
  }

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

  return i + 1;
};

먼저, 배열의 가장 첫번째 원소를 가리키는 i 포인터와 i 포인터 다음 원소를 가리키는 j 포인터가 있습니다. 만약 i와 j가 가리키는 원소가 서로 같으면, j 포인터를 오른쪽으로 이동시킵니다. 그러나 i와 j가 가리키는 원소가 서로 다르면, i 포인터를 오른쪽으로 이동시키고, i 포인터가 가리키는 자리에 j 포인터가 가리키는 원소를 덮어씌우면 됩니다. 이렇게 하면 i 포인터는 중복되지 않는 원소의 개수를 가리키게 됩니다.

포인터 패턴을 사용하면 중복을 제거한 원소의 개수를 효율적으로 계산할 수 있습니다.