Multiple pointer

멀티 포인터 패턴은 정렬된 배열에서 한 쌍을 검색하는 데에 효과적인 패턴이다. 이 패턴은 인덱스나 위치에 해당하는 포인터 혹은 값을 만든 후 특정 지점으로 이동시킨다. 한 쌍의 값이나 조건을 충족시키는 무언가를 찾기 위한 패턴이다.

정렬된 배열에서 두 가지 숫자를 받아와, 0이 되는 값을 찾는 로직을 작성하기 위해서는 일반적으로 2중 루프를 사용할 수 있지만, 마찬가지로 시간 복잡도 면에서 좋지 않다.

다중 포인터 패턴을 사용해 보자.

const sumZero = (arr) => {
  let left = 0; // 포인터 1
  let right = arr.length -1; // 포인터 2
  
  while(left <= right) { // 같은 값을 가리키면 stop
    let sum = arr[left] + arr[right]; // 가리킨 값의 합
    if(sum === 0) {
    	return [arr[left], arr[right]];
    } else if(sum > 0) { // 정렬되어 있으므로 합한 값이 0 이상이면 큰 값(right)을 줄임
    	right--;
    } else {
    	left--;
    }
  }
  
}

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

위의 예시처럼 포인터를 두 개를 설정하고 두 값을 비교하면, 이중 반복문 사용 없이 원하는 답을 구할 수 있다.

이러한 패턴으로 중복되지 않은 값이 몇 개가 되는지 직접 작성해 본 코드는 다음과 같다.

function countUniqueValues(arr) {
  let i = 0;
  let j = 1;
  let answer = 0;

  while (j <= arr.length) {
    if (arr[i] !== arr[j]) {
      i = j;
      j++;
      answer++;
    } else if (arr[i] === arr[j]) {
      j++;
    }
  }

  return answer;
}

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

i와 j로 각각 두 인덱스를 가리킨다. 만약 두 값이 같은 값이면 다른 값이 나올 때까지 j에 숫자를 더해준다. 만약 같은 값일 경우, i에 j를 넣고, j에 숫자를 더한다. 이런 식으로 j가 배열의 길이와 일치할 때까지 더해준다.

이 패턴대로 하면 이중 루프를 사용할 필요가 없기 때문에 시간복잡도가 낮아지는 효과적인 코드를 작성할 수 있다.