[알고리즘] 빈도수 세기 알고리즘 (Frequency Counter)

카테고리 : 컴퓨터 공학
태그: cs · 컴퓨터 공학 · algorithm · Frequency Counter · 빈도수 세기 · Refactored

1. 빈도수 세기 알고리즘 (Frequency Counter)

문제 설명

  • 빈도수 세기 (특정 문자열, 배열 등이 주어졌을 때 요소들의 빈도 수를 체크한다)

제한사항

  1. 두 개의 배열을 허용하는 same 이라는 함수를 작성한다.
  2. 첫 번째 배열의 모든 값이 두번째 배열에 순서와 무관하게 제곱되어 포함될 경우 true 를 반환한다.
  3. 단, 빈도는 동일해야 한다.

입출력 예

arr1arr2result
[1, 2, 3][4, 1, 9]true
[1, 2, 3][1, 9]false
[1, 2, 1][4, 4, 1]false

2. My Solution

1) 기본 접근법으로 해결 ( For loop 내에서 indexOf를 사용)

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) {
    //첫번째 배열 , 두번째 배열의 크기가 다른 경우 false 반환
    return false;
  }
  for (let i = 0; i < arr1.length; i++) {
    let correctIndex = arr2.indexOf(arr1[i] ** 2);
    if (correctIndex === -1) {
      return false;
    }
    arr2.splice(correctIndex, 1);
  }
  return true;
}
  • indexOf()메서드는 배열에서 지정된 요소를 찾을 수 있는 첫 번째 인덱스를 반환하고 존재하지 않으면 -1을 반환
  • splice()메서드는 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경

시간 복잡도 O(n2) : For Loop 내에서 IndexOf를 사용하여 중첩 루프가 사용됌

3. Refactored Solution

1) 두개의 loop 를 사용 (시간 복잡도를 O(n)으로 유지할 수 있다.)

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) {
    return false;
  }

  let counter1 = {};
  let counter2 = {};

  for (let item of arr1) {
    counter1[item] = (counter1[item] || 0) + 1;
  }
  for (let item of arr2) {
    counter2[item] = (counter2[item] || 0) + 1;
  }

  for (let key in counter1) {
    if (!(key ** 2 in counter2)) {
      return false;
    }

    if (counter2[key ** 2] !== counter1[key]) {
      return false;
    }
  }
  return true;
}
console.log(same([1, 2, 3, 2], [9, 1, 4, 4]));
  • in 연산자; ****명시된 key값이 명시된 객체에 존재하면 true 반환
  • for..of 객체의 모든 열거할 수 있는 item의 개수만큼 반복
  • for..in 키가 지정된 모든 열거 가능한 key에 대해 반복

시간 복잡도 O(N) : Nested loop가 아닌 두개의 loop 를 사용

빈도 카운터의 개념은 보통 객체를 사용한 다는 것이 핵심

두 배열을 객체로 쪼개 만든 후 분류하여 두 객체를 비교한 방식

중첩된 반복문을 사용하는 것 보다는 두개의 반복문을 사용하는것이 더 좋다(O(n))