[알고리즘] 다중 포인터 알고리즘 활용 (Multiple Pointers)

카테고리 : 컴퓨터 공학
태그: cs · 컴퓨터 공학 · algorithm · 다중 포인터 · Refactored · Multiple Pointers · 고유값 세기

1. 다중 포인터 알고리즘 활용 (Multiple Pointers)

문제 설명

  • 정렬된 배열을 받아들이고 배열의 고유 값을 세는 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

2. My Solution

1) forEach로 모든 배열 요소 순회

  • includes()로 중복된 값을 제외하고 result 배열에 요소를 추가함
function countUniqueValues(arr) {
  let result = [];
  arr.forEach((item) => {
    if (!result.includes(item)) {
      result.push(item);
    }
  });
  return result.length;
}

시간 복잡도 O(n) : arr.forEach를 사용하여 배열을 순회 , O(n)만큼의 시간 복잡도를 구현했다

공간 복잡도 O(n) : 배열길이의 비례해서 O(n)만큼의 공간 복잡도를 구현했다

3. Insight Solution

1) for문 순회 반복

  • arr의 요소를 찾고 i값을 0으로 초기화
  • 중복값을 arr[i]와 arr[j]로 비교
  • true값일때 i 값을 늘려주는 방법
function countUniqueValues(arr) {
  let i = 0;
  for (let j = 1; j < arr.length; j++) {
    if (arr[i] !== arr[j]) {
      i++;
      arr[i] == arr[j];
    }
  }
  return i + 1;
}

시간 복잡도 O(N)