다중 포인터 패턴

JavaScript 알고리즘 & 자료구조 마스터 클래스 강의를 듣고 작성하는 강의노트

• 다중 포인터(Multi Pointers)라는 명칭은 공식 명칭이 아니다. 본 글에서는 이를 '다중 포인터'라고 명명한다.

다중포인터의 개념

인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간 지점에서 부터 시작, 끝, 양쪽 지점을 향해 이동시키는 것이다. 즉, 배열이나 문자열과 같은 일종의 선형 구조나 이중 연결 리스트, 단일 연결 리스트를 만든다.

간단한 예제 1

오름차순으로 정렬된 배열을 인자로 받는 sumZero 함수로, 합계가 0인 첫번째 쌍을 찾는다.

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

흔한 해결책

• 시간 복잡도 O(N2)
• 공간 복잡도 O(1)

Nested loop 로 시간 복잡도 효율성이 떨어진다.

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]];
      }
    }
  }
}

리팩토링

두 개의 포인터를 사용한 리팩토링 솔루션이다.

하나는 왼쪽에서 0 의 인덱스에서 시작하고, 다른 하나는 배열의 마지막 인덱스에 시작한다.

• 시간 복잡도 O(N)
• 공간 복잡도 O(1)

function sumZero(arr) {
  //왼쪽 인덱스 포인터 지정
  let left = 0;
  //오른쪽 인덱스 포인터 지정
  let right = arr.length - 1;
  //while문 설정 조건은 왼쪽이 오른쪽보다 크다.
  //만약 조건문이 참이라면, while문 안의 문장들이 실행된다. 거짓이라면, 문장은 그냥 while 반복문 후로 넘어간다.
  while (left < right) {
    //합계지정
    let sum = arr[left] + arr[right];
    if (sum === 0) {
      return [arr[left], arr[right]];
    } else if (sum > 0) {
      right--;
    } else {
      left++;
    }
  }
}

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