Frequency Counter

frequency counter pattern은 일반적으로 문자열이나 배열을 사용한 문제 해결 패턴 중에 하나다. 이 패턴은 주로 데이터를 비교하는 데에 사용된다.

이 방식을 사용하면 중첩 반복문 사용을 피할 수 있어 시간 복잡도를 O(N²)에서 O(N)까지 낮추는 데에 도움이 된다.

다음과 같은 문제가 있다.

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

same 함수는 2개의 배열을 인수로 받고, 만약 두번째 배열의 값이 첫 번째 배열의 값의 제곱근을 가지고 있다면, true를 반환한다.

Frequency Counter를 사용해서 해결하기

가장 일반적인 방법으로는 하나의 배열에 루프를 적용하고, 그 안에서 두 번째 배열에 또다시 루프를 적용하는 방법을 떠올릴 수 있다. 그러나 이 방식으로는 시간복잡도가 O(N²)이 되므로 빅오 표기법으로 판단했을 때 그리 좋은 알고리즘이라고 볼 수 없다.

다음은, 빈도 수 카운터 패턴을 적용한 방식이다.

const same = (arr1, arr2) => {
	if(arr1.length !== arr2.length) {
	    return false;
    }
  
  let frequencyCounter1 = {};
  let frequencyCounter2 = {};
  
  for(let val of arr1) {
  	frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
  }
  
  for(let val of arr2) {
  	frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1
  }
  
  for(let key in frequencyCounter1) {
  	if(!(Math.pow(frequencyCounter1[key], 2) in frequencyCounter2)) {
      return false;
    }
  }
}

Frequency Counter를 사용해서 배열이나 문자열을 사용할 때, 시간 복잡도를 낮춰보자. 이 패턴은 주로 객체를 사용한다. 객체나 문자열을 객체로 만들어 비교하면 더 빠른 비교가 가능하다.