다중 포인터 패턴

다중 포인터

• 배열이나 문자열 같은 선형 구조에서 각자 다른 원소를 가리키는 2개의 포인터를 조작해가면서 원하는 것을 얻어내는 개념.
• 값이나 조건을 충족시키는 한 쌍을 찾아가는 개념.
  
  
  
  
  
  

sumZero 함수 예제를 살펴 보자.

정렬된 배열에서 첫번째로 합이 0이 되는 쌍을 찾는 함수이다.
두 포인터가 하나는 처음, 하나는 끝 인덱스에서 중앙으로 이동하면서 쌍을 찾는다.

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

Naive solution

이중 루프를 통한 방법이다. 시간 복잡도는 O(N^2)이다.
배열의 길이가 길어질수록 반복횟수가 제곱으로 늘어나게 된다.

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

Refactor

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

const arr = [-3, -2, -1, 0, 1, 2, 5];

가장 왼쪽에 있는 값(left)과 가장 오른쪽에 있는 값(right)의 합이 0이 되는 쌍을 찾는다.

1. left가 -3이고 right는 5이므로 둘의 합은 2이다. 두 수의 합이 0보다 크므로 right를 왼쪽으로 한 칸 옮긴다.
2. left는 -3, right는 2가 되므로 둘의 합은 -1이다. 두 수의 합이 0 보다 작으므로 left를 오른쪽으로 한 칸 옮긴다.
3. left는 -2, right는 2가 되었다. 두 수의 합이 0 이 되므로, 이 한 쌍을 출력한다.

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++;
    }
  }
  // 값을 못찾았다면 defult로 undefined가 리턴 된다.
}

시간 복잡도는O(N)으로 해결할 수 있다.

---

---

countUniqueValues

정렬된 배열에서 요소의 가짓수를 구하는 함수가 있다.
두 포인터가 첫번째 혹은 마지막에서 같은 방향으로 이동한다.

console.log(countUniqueValues([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([1])); // 1
console.log(countUniqueValues([-2, -1, -1, 0, 1])); // 4

풀이방법

function countUniqueValues(arr) {
  let i = 0;
  let j = 0;
  if (!arr.length) return 0;

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

const arr = [1, 1, 1, 1, 1, 2];
i
[1, 1, 1, 1, 1, 2]
 j							// arr[i]와 arr[j]는 같으므로 j++
 
 i
[1, 1, 1, 1, 1, 2]
    j						// arr[i]와 arr[j]는 같으므로 j++
    
 i
[1, 1, 1, 1, 1, 2]
       j					// arr[i]와 arr[j]는 같으므로 j++

 i
[1, 1, 1, 1, 1, 2]
          j					// arr[i]와 arr[j]는 같으므로 j++
          
 i
[1, 1, 1, 1, 1, 2]
             j				// arr[i]와 arr[j]는 같으므로 j++
             
 i
[1, 1, 1, 1, 1, 2]
                j			// arr[i]와 arr[j]는 다르므로 i++ 후 arr[i]에 arr[j]를 대입 j++		

    i
[1, 2, 1, 1, 1, 2]
                   j        //j < arr.length를 만족하지 않으므로 while문 탈출
                			//i의 i + 1(가짓수)을 리턴한다.

풀이방법 2

또한 Set과 spread 연산자를 활용하여 간단하게 해결 할 수도 있다.

const solution = arr => {
  const uniqueArr = [...new Set(arr)];
  return uniqueArr.length;
};