[20일차]Multiple Pointers Pattern 2

서론

첫 Multiple Pointers Pattern 글에서는 다중 포인터 패턴이 어떤것인지에 대해 공부했다. 오늘은 그것을 이용해서 하나의 배열에서 중복을 제거한 고유한 값이 몇 개인지를 알아내는 문제를 풀어보도록 하겠다.

본론

다중 포인터 패턴을 이용하기 위해서는 일단 두 개의 선행조건이 반드시 필요하다.

• 선형의 자료구조일 것.
• 정렬되어있을 것.

Multiple Pointers - countUniqueValues

Implement a function called countUniqueValues, which accepts a sorted array, and counts the unique values in the array. There can be negative numbers in the array, but it will always be sorted.

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)

나는 다중 포인터 패턴을 이용해 이런 식으로 해답을 작성했다.

function countUniqueValues(arr){
  // add whatever parameters you deem necessary - good luck!
  var i = 0; 
  if(arr.length === 0) return 0;  
  for(var j = 1; j<arr.length; j++){

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

다중 포인터 패턴은 두 개의 포인터를 이용해 한 방향으로 이동시키며 값을 비교하는 해결방법이다.
처음에 i와 j를 세팅 해 놓은 뒤, 한 방향으로 같이 움직이면서 기존의 배열을 변형시켜 O(n)의 시간복잡도의 해결방법을 만들어냈다. 자세한 풀이는 다음과 같다.

[1,1,1,2,2,3,5,6,7,7,8,10,10,10]

만약 이런 식의 배열이 매개변수로 들어왔다고 하면 포인터가 이렇게 설정된다.

 i
[1,1,1,2,2,3,5,6,7,7,8,10,10,10]
   j

서로 값을 비교한다. 값이 일치하는 경우 j의 포인터만 앞으로 움직인다. 그 다음도 마찬가지로 j만 인덱스를 하나 더 추가하여 이동한다.

 i
[1,1,1,2,2,3,5,6,7,7,8,10,10,10]
     j

이번에는 값이 다르다.

 i
[1,1,1,2,2,3,5,6,7,7,8,10,10,10]
       j

이렇게 되면 i의 인덱스를 증가시키고 그 자리에 해당 값을 넣는다.

   i
[1,2,1,2,2,3,5,6,7,7,8,10,10,10]
       j

이런식으로 계속해서 비교한다.

   i
[1,2,1,2,2,3,5,6,7,7,8,10,10,10]
         j
         
     i
[1,2,3,2,2,3,5,6,7,7,8,10,10,10]
           j       
           
       i
[1,2,3,5,2,3,5,6,7,7,8,10,10,10]
             j    
.
.
.

이렇게 계속 비교하며 배열을 변형시키다 보면, 고유한 값들을 앞에서부터 i까지 정렬하게 된다. 이때 i를 반환하면 된다. 물론 배열의 인덱스는 0부터 시작하니 +1을 해서 말이다!

               i
[1,2,3,5,6,7,8,10,7,7,8,10,10,10]
                       j     

//return 8                       

참고

https://www.udemy.com/share/105zfq3@mWPCFcH1J7J-QsAQ_hRXCLFu3MtOxrpHAa8PeM_MvI4y5GqbwB-uO18MojJGJ3-a5Q==/