Multiple Pointers

이번에는 multiple pointers라는 알고리즘에 대해 정리해봅니다. 정렬된 배열에 합이 0인 값을 찾거나 중복된 값을 제거하고 배열의 길이를 반환하는 등의 알고리즘을 풀이하기 위해서 많은 경우에는 nested loops를 사용하게 됩니다.

그러나 nested loops는 시간 복잡도가 O(n²)이므로 가장 피해야할 알고리즘 풀이 방법입니다. 두 가지의 예제를 통해 이러한 문제를 해결할 multiple pointers라는 알고리즘에 대해 알아보도록 합시다.

sumZero

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

sumZero는 배열을 인수로 받아 두 수의 합이 0인 배열의 값을 찾아내는 알고리즘 문제입니다. 먼저 nested loops를 사용한 방법과 multiple pointers를 활용한 풀이 방법에 대해 알아봅시다.

Solution (1) - nested loops

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

위 방법은 Big O가 O(n²)인 nested loops를 활용한 풀이 방법입니다. 실제로 leetcode를 통해 문제를 풀이하였을 때, 이러한 방식으로 풀이를 많이 했었던 기억이 납니다.

물론, 잘못된 풀이 방법은 아니고 저와 같은 초보 개발자들은 반복문에 대한 이해도가 필요하기 때문에 이러한 방식 또한 알아야한다고 생각합니다. 그러나 추후 실무를 하게 된다면, 많은 데이터를 다루게 될테고 이러한 방식은 애플리케이션의 속도를 느리게 하는 가장 주된 원인이 될 것입니다.

이를 해결하기 위해서 nested loops 방식은 최대한 피해야하므로 multiple pointers에 대해 알아보도록 합시다.

Solution (2) - multiple pointers

function sumZero(arr) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    if (arr[left] + arr[right] < 0) {
      left++;
    } else if (arr[left] + arr[right] > 0) {
      right--;
    } else {
      return [arr[left], arr[right]];
    }
  }
}

multiple pointers를 활용한 풀이 방법입니다. 이는 말그대로 포인터가 여러 개가 있다는 뜻이 됩니다. 위의 예시를 보면, 배열의 숫자들을 가리키는 포인터가 left, right 두 개가 있습니다.

반복문은 left가 right보다 작을 때까지를 반복하게 되며, 두 수의 합을 비교합니다. 두 수의 합이 0이면 배열을 반환하게 되고, 0보다 크면 right 값을 줄여나가고 작으면 left 값을 늘리는 방식으로 진행됩니다.

이렇게 nested loops를 피하게 되고 시간 복잡도는 O(N), 그리고 공간 복잡도는 O(1)이 될 수 있습니다.

countUniqueValues

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

이번에도 multiple pointers를 활용할 수 있는 예제입니다. 인수로 배열이 주어지며, 함수의 이름에서 알 수 있다시피 중복된 배열의 값을 제거하고 유일한 배열의 값의 길이를 반환하는 함수입니다. 다소 복잡하게 풀이가 진행되지만 한 번 이해만 하게 되면 쉬운 코드 진행입니다.

Solution (1) - multiple pointers

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

이 방식 또한 포인터가 i, j 두 개이다. arr[i], arr[j]가 가리키는 두 값이 같으면, j만 증가시키게 되고 반대로 두 값이 다르면 i를 증가시켜서 해당 arr[i]값에 arr[j]를 할당한다.

그리고 마지막 결과값으로 i+1 값을 반환하면 알고리즘을 풀이하게 된다. 이렇게 말해서는 도저히 이해가 가지 않기 때문에 예를 들어 살펴보도록 하자.

countUniqueValues([1, 1, 1, 2, 2, 3])

1. j = 1 (i = 0)
 i
[1, 1, 1, 2, 2, 3]
    j
두 값을 비교하게 되고, 두 값은 같다. 그러면 j만 1을 증가시킨다.

2. j = 2 (i = 0)
 i
[1, 1, 1, 2, 2, 3]
       j
이번에도 두 값이 같으므로 j를 1 증가!

3-1. j = 3 (i = 0)
 i
[1, 1, 1, 2, 2, 3]
          j
이번에는 드디어 두 값이 다르다. 이렇게 되면, i를 1 증가시키게 된다.

3-2. j = 3 (i = 1)
    i
[1, 2, 1, 2, 2, 3]
          j
그리고 i를 증가시켜서 이동한 값에 j의 자리에 있는 값을 할당한다. 그래서 해당 값은 2가 된다.
이후 자연스럽게 for 반복문에 의해 j는 1이 증가하게 된다.

4. j = 4 (i = 1)
    i
[1, 2, 1, 2, 2, 3]
             j
그리고 또 두 값을 비교하게 된다. 이번에는 두 값이 같으므로 j만 1 증가한다.

5-1. j = 5 (i = 1)
    i
[1, 2, 1, 2, 2, 3]
                j
이번에는 두 값이 다르다. 그렇게 되면? i를 1 증가시킨다.
5-2. j = 5 (i = 2)
       i
[1, 2, 3, 2, 2, 3]
                j
i를 이동하고 arr[i]에 arr[j]를 할당한다. j가 마지막까지 이동했으므로 for 반복문은 정지한다.
이후 살펴보면, 중복된 값을 제거한 배열은 i가 이동을 마친 [1, 2, 3]임을 알 수 있다.
여기서 현재 i의 값은 2이므로 여기에 1을 더한 3이 해당 배열의 길이인 것이다.

그러므로 i + 1을 리턴하면 정답이 되는 것이다! 😎

Solution (2) - new Set

function countUniqueValues(arr) {
  const newSet = new Set(arr);
  return newSet.size;
}

위 풀이 방식은 인수의 중복 값을 제거하는 Set 객체를 활용한 방법입니다. 해당 문제를 보자마자 바로 Set이 생각나서 위와 같은 방식으로 해결하였습니다. 이 또한 시간복잡도가 O(1)이므로 더욱 간단한 방법이라고 생각한다.