자바스크립트 - 다중 포인터 패턴 (Multiple Pointer)

다중 포인터 패턴이란?

다중 포인터 패턴은 위치에 해당하는 값 각 조건에 따라서 끝이나, 중간으로 이동하는 패턴입니다.

 

예시 1

오름 차순으로 정렬된 배열에서 합계가 0인 첫 번째 쌍 구하시오

풀이 1

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


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

 

이중 for문을 사용하여 해결할 수 있지만, 이렇게 사용하면 시간 복잡성이 O(n2)가 된다.

 

풀이 2

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

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

 

위와 같이 다중 포인터 패턴을 이용하여 풀이를 할 수 있다.

1. 배열의 첫 번째와 끝에 index  값을 구해서 시작한다.

2. -4 + 10 = 6 양수 일 경우에는 끝의 index 값을 하나 줄인다.

(이미 정렬이 된 배열이기 때문에 값을 0으로 만들기 위해서는 하나 줄인다.

3. -4 + 3 = -1 음수 일 경우에는 첫번째 index의 값을 하나 올린다.

4. 0이 되면 해당 값을 return;

 

이렇게 문제를 풀게 되면 시간 복잡성을 O(n)으로 줄일 수 있게 된다.

 

예시 2

정렬된 배열을 받아들이고 배열의 고유 값을 세는 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([-2,-1,-1,0,1]) // 4

 

Time Complexity - O(n)
Space Complexity - O(n)

 

풀이 1

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

 

1. i, j를 0과 1 index에서 시작

2. 고유한 값이 있으면 i를 하나 올리고 그 자리에 j 값을 넣음

[1, 1, 1,  2, 3, 3] 일 경우 [1, 2, 3,1, 1, 3]으로 배열이 종료하게 됨

3. i = 3;