빈도수 세기 패턴

JavaScript 알고리즘 & 자료구조 마스터 클래스 강의를 듣고 작성하는 강의노트

문제해결 패턴 - 빈도수 세기

말 그대로 특정 문자열, 배열 등이 주어졌을 때 요소들의 빈도 수를 체크하여 풀어내는 방식이다. 간단한 예제를 통해 알아보자.

Example

1. 두 개의 배열을 허용하는 same 이라는 함수를 작성한다.

2. 첫 번째 배열의 모든 값이 두번째 배열에 순서와 무관하게 제곱되어 포함될 경우 true 를 반환한다.

3. 단, 빈도는 동일해야 한다.

same([1, 2, 3], [4, 1, 9]); // true
same([1, 2, 3], [1, 9]); // false
same([1, 2, 1], [4, 4, 1]); // false, 빈도가 동일해야 한다.

Solution

가장 일반적인 접근법으로 For loop 내에서 indexOf를 사용해
Nested loop(중첩된 루프)가사용되고 있어 시간 복잡도는 O(n2) 이다.

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) {
    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()메서드는 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경합니다

Nested loop 보다 두개의 loop 를 사용하는 것이 좋다. 이는 시간 복잡도를 O(n)으로 유지할 수 있다.

Refactored (Frequency Counter)

시간 복잡도 O(n)

function same(arr1, arr2) {
  ///1 .arr1과 arr2의 길이가 다르면 false
  if (arr1.length !== arr2.length) {
    return false;
  }
  ///빈도 수를 정의 하기 위한 임의의 객체 2개를 생성
  let frequencyCounter1 = {};
  let frequencyCounter2 = {};
  /// arr1의 요소를 frequencyCounter1 키값에 넣어주고 +1씩 값을 준다
  for (let val of arr1) {
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
  }
  ///arr2의 요소를 frequencyCounter2 키값에 넣어주고 +1씩 값을 준다
  for (let val of arr2) {
    frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
  }
  ///frequencyCounter1 의 키의 제곱이 frequencyCounter2에 없다면 false반환
  for (let key in frequencyCounter1) {
    if (!(key ** 2 in frequencyCounter2)) {
      return false;
    }
    ///frequencyCounter2안의 frequencyCounter1 키 제곱의 밸류(빈도) 가 frequencyCounter1 의 밸류(빈도)가 다르다면 false반환
    if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
      return false;
    }
  }
  ///모든 조건을 통과하면 true 반환
  return true;
}

same([1, 2, 3, 2], [9, 1, 4, 4]);

이처럼 빈도 카운터의 개념은 보통 객체를 사용한 다는 것이 핵심이다.두 배열을 객체로 쪼개 만든 후 분류하여 두 객체를 비교한 방식이다.

객체를 사용하여 프로파일을 구성하는 것은 배열이나 문자열의 내용을 분석하는 방법으로 보통 배열이나 문자열과 같은 선형 구조를 구성하는 것이다. 이는 해당 분석을 문자열이나 배열에서 생성된 다른객체의 형태와 신속하게 비교할 수 있다.

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