2.2Multiple Pointers

Multiple Pointers

Multiple Pointers 패턴은 배열의 양 끝이나 특정 위치에서 시작한 두 개 이상의 포인터(pointer)를 조건에 따라 이동시키며 문제를 해결하는 방식이다.

이 방식은 일반적으로 정렬된 배열에서 자주 사용되며, 불필요한 중첩 루프를 줄여 시간 복잡도를 획기적으로 개선할 수 있다. 또, 별도의 공간을 거의 사용하지 않기 때문에 공간 복잡도 또한 매우 효율적이다.

예시 1: sumZero

정렬된 정수 배열이 주어졌을 때, 합이 0이 되는 첫 번째 쌍(pair)을 찾아 반환하라. 없으면 undefined를 반환한다.

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

비효율적인 풀이

가장 먼저 떠오를 수 있는 접근 방식은 아래와 같다.

javascript
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²)이다.

효율적인 방법: Multiple Pointers

더 효율적인 방법은 아래와 같이 여러개의 포인터를 사용하는 것이다. 즉, 정렬된 배열이라는 점을 이용해 맨 왼쪽과 오른쪽으로 포인터를 나눠서 한 번의 루프로 해결한다. 시간 복잡도는 O(n)이 된다.

javascript
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++;
    }
  }
}

예시 2: Count Unique Values

정렬된 배열이 주어졌을 때, 고유한(unique) 값의 개수를 반환하라.

javascript
countUniqueValues([1, 1, 1, 1, 1, 2]) // 2
countUniqueValues([1, 2, 3, 4, 5, 7, 12]) // 7
countUniqueValues([]) // 0
countUniqueValues([-2, -1, -1, 0, 1]) // 4

Multiple Pointer 알고리즘을 통해 아래와 같이 풀 수 있다. 하나의 포인터로 우선 고유 값을 저장하고, 다른 포인터는 루프를 순회하며 첫 포인터와 값을 비교한다.

javascript
function countUniqueValues(arr){
  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;
}

---

🤠 개인 탐구

Count Unique Values 문제 내 풀이 복기

나는 이렇게 풀었다. 역시나 지난번처럼 첫 예시(이번 경우는 sumZero)를 활용한 방식이다.

javascript
function countUniqueValues(arr){
  if(arr.length === 0) return 0;
  let left = 0;
  let right = 1;
  let counter = 1;
  while(right < arr.length){
    if(arr[left] === arr[right]) {
        right++;
      } else {
        left = right;
        counter++;
        }
    }
  return counter;
}

추가 문제1: isSubsequence

두 문자열을 받아, 첫번째 문자열이 두번째 문자열을 이루는 부분인지 확인하는 isSubsequence 함수를 작성하라. 아래와 같이, 첫번째 문자열은 두번째 문자열에 순서가 바뀌지 않은 상태로 나타나야 한다.

javascript
isSubsequence('hello', 'hello world'); // true
isSubsequence('sing', 'sting'); // true
isSubsequence('abc', 'abracadabra'); // true
isSubsequence('abc', 'acb'); // false (order matters)

나는 이렇게 풀었다:

javascript
function isSubsequence(str1, str2){
    const str1Arr = str1.split("")
    const str2Arr = str2.split("")
    let pointer = 0
    for(let i = 0; i<str2Arr.length; i++){
        if(str1Arr[pointer] === str2Arr[i]){
            if(pointer === str1Arr.length -1){
                return true
            }
            pointer++
        } 
    }
    return false
}

이후에 알게되었지만,

• 굳이 split("")으로 배열을 만들 필요 없이, 문자열 자체가 인덱싱하는게 낫다.
• pointer를 i와 함께 바로 1 증가시키면 str1Arr.length -1과 비교할 필요 없이 문자열 길이와 바로 비교할 수 있다.

javascript
function isSubsequence(str1, str2) {
    let pointer = 0;
    for (let i = 0; i < str2.length; i++) {
        if (str1[pointer] === str2[i]) {
            pointer++;
            if (pointer === str1.length) return true;
        }
    }
    return false;
}

(강의에서 제시한) 답안은 아래와 같다. while문으로 2번째 문자열의 각 문자를 루프하는데, 사실상 내 풀이와 같은 방식이라고 생각한다.

javascript
function isSubsequence(str1, str2) {
  let i = 0, j = 0;
  if (!str1) return true;
  while (j < str2.length) {
    if (str2[j] === str1[i]) i++;
    if (i === str1.length) return true;
    j++;
  }
  return false;
}

다음 섹션에서 다룰 Recursion, 즉 재귀를 활용하는 풀이도 있다:

javascript
function isSubsequence(str1, str2) {
  if (str1.length === 0) return true
  if (str2.length === 0) return false
  if (str2[0] === str1[0]) return isSubsequence(str1.slice(1), str2.slice(1))
  return isSubsequence(str1, str2.slice(1))
}

이 방식은 코드가 간결하지만, 두 가지 문제가 있다:

1. slice() 연산이 매 호출마다 새 문자열을 복사하므로 추가 비용이 발생한다.
2. 자바스크립트는 tail call optimization(꼬리 재귀 최적화)을 보장하지 않기 때문에, 재귀 깊이에 따라 Call Stack Overflow 위험이 있다.

따라서 꼬리 재귀(Tail Recursion)으로 고쳐 메모리 효율을 개선할 수는 있으나, 자바스크립트에선 여전히 최적화가 되지 않으므로 반복문이 이 경우는 보다 좋은 방식(성능이 좋으며 안정적)이라고 할 수 있다.

재귀와 관련된 보다 자세한 내용은 재귀 섹션에서 알아보자.

추가 문제2: findPair

정렬되지 않은 배열과 숫자 n이 주어졌을 때, 배열 안에서 n만큼 차이가 나는 쌍이 있는지 찾는 알고리즘을 작성하라.

javascript
findPair([6,1,4,10,2,4], 2) // true
findPair([6,1,4,10,2,4], 22) // false
findPair([], 0) // false
findPair([5,5], 0) // true
findPair([-4,4], -8) // true

이 문제는 우선 배열을 sort하고, n값이 0일때와 아닐 때로 나누어 풀었다. sort를 사용했기에 시간 복잡도는 n log n이고, 공간 복잡도는 O(1)이다.

javascript
function findPair(arr, diff){
  if(arr.length < 2) return false;
    
  // 주의: 아래에서 언급하겠지만, 실무에선 arr.slice().sort(...)처럼 얕은 복사를 하는게 더 일반적
  const sortedArr = arr.sort((a,b)=> a - b);
  // diff가 0일때, 배열 안에 중복된 값 여부로 판단
  if(diff === 0){
    for (let i = 0; i < sortedArr.length - 1; i++) {
      if (sortedArr[i] === sortedArr[i + 1]) return true;
    }
    return false;
  }

  // diff가 0이 아닐 때 
  let left = 0, right = 1;
  const absDiff = Math.abs(diff);
    
  while (left < sortedArr.length && right < sortedArr.length) {
    if (left === right) {
      right++; // 같은 위치일 땐 right만 이동
      continue;
    }

    const currentDiff = Math.abs(sortedArr[right] - sortedArr[left]);

    if (currentDiff === absDiff) return true;
    else if (currentDiff < absDiff) right++;
    else left++;
  }

  return false;
}

다만, 단일 문제로 나왔으니깐 이렇게 풀었지 실제 프로젝트 내였으면 sortedArr를 만들 때 arr.slice().sort(...)로 얕은 복사를 해야할 가능성이 높다. O(n)의 메모리를 사용하게 되지만, arr에 바로 sort를 하면 원본 배열에 변형이 가서 예상치 못한 사이드 이펙트가 발생할 수도 있기 때문이다.

강의 자료에선 이렇게 풀었다. n을 0일때, 아닐때로 나누어 푼것은 동일한데 Set을 활용해 sort할 필요 없이 중복값과 차이값을 계산했다. 이럴 경우 for 루프를 쓰고 Set에 저장하므로 O(n)의 공간 복잡도와 O(n)의 시간 복잡도를 가진다.

javascript
function findPair(arr, n) {
  // if n is 0, we just need to see if there's any duplicate in the array
  if (n === 0) {
    const seen = new Set();
    for (let num of arr) {
      if (seen.has(num)) {
        return true;
      }
      seen.add(num);
    }
    return false;
  }
 
  // for non-zero n, place all elements in a set
  const setVals = new Set(arr);
 
  // check for val + n or val - n in the set
  for (let val of arr) {
    if (setVals.has(val + n) || setVals.has(val - n)) {
      return true;
    }
  }
 
  return false;
}

내 풀이와 비슷한 방식의, sort를 활용한 모범 답안도 있었다:

javascript
function findPair(arr, num) {
  arr.sort((a, b) => a - b);
  let i = 0;
  let j = 1;
  while (i < arr.length && j < arr.length) {
    if (i !== j && Math.abs(arr[j] - arr[i]) === Math.abs(num)) {
      return true
    } else if (arr[j] - arr[i] < num) {
      j++
    } else {
      i++
    }
  }
  return false;
}

자바스크립트의 반복문들 비교

알고리즘 문제를 풀다보니 많은 루프(반복)문들을 작성하게 된다. 간단하게 개념 정리를 하고 넘어가자.