다중 포인터 패턴

Multiple Pointers: 다중 포인터 (공식 이름은 아님)

인텍스나 위치에 해당하는 포인터 또는 값을 만든 다음에 특정 조건에 따라 중간 지점에서부터 시작 지점, 끝 지점 또는 양쪽 지점을 향해 이동시키는 것이다.

 

공간 복잡성을 최소화하면서 문제를 해결하는데에 매우 효율적이다.

포인터는 배열이나 문자열의 특정 위치를 가리키는 것이다.

 

예시 1: sumZero함수

입력 값: 오름차순으로 정렬된 정수 배열

출력 값: 합계가 0인 첫 번째 쌍. 쌍이 없을 경우 0으로 합한 값 또는 undefined

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

 

순진한 해결책

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

시간 복잡도 - O(N^2)

공간 복잡도 - O(1)

 

아래는 두 개의 포인터를 사용한 리팩토링된 해결책이다.

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

시간 복잡도 - O(N)

공간 복잡도 - O(1)

 

 

예시2: countUniqueValues

입력값: 정렬된 정수 배열

출력값: 고유한 값의 개수를 반환

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

 

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

 

위 코드는 i와 j라는 두 개의 포인터가 사용되었고 j와 i가 다를 경우 i의 값에 +1 시켜주고 i의 value를 교체해주었다.

O(N)의 시간 복잡도를 가진다.

 

다중 포인터는 정렬된 상태에서 사용하며 예제를 보며 익히는 게 좋을 것 같다.