유니크 값 세기

문제 설명

countUniqueValues 라는 함수를 구현하여 정렬된 배열을 전달하면 해당 배열의 고유한 값의 개수를 반환하도록 한다. 배열에는 음수가 포함될 수 있지만 항상 정렬된 상태이다.

예시는 다음과 같다.

countUniqueValues([1,1,1,1,1,2]); // 2
countUniqueValues([1,2,3,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;
  let i = 0;
  for (let j = 1; j < arr.length; j++) {
    // 루프를 돌면서 arr[i]와 arr[j]의 각 위치(index)에 따른 값을 비교한다.
    // 둘이 같다면 아무 작업도 해주지 않는다. j는 루프로 인해 자동으로 증가한다.
    if (arr[i] !== arr[j]) {
      i++;
      arr[i] = arr[j];
    }
  }
  return i + 1;
};

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

시간복잡도는 On 이다.