[JS 알고리즘&자료구조] 빈도수 세기 패턴

오늘 배울 패턴을 강의에서는 빈도수 계수기(Frequency Counter)라고 명명하지만 사실 해당 패턴에 해당 공식 명칭이 있는 것은 아니다. 해당 패턴은 여러 데이터와 입력값이 서로 비슷한 값인지, 서로 간의 아나그램인지, 값이 다른 값에 포함되는 비교하거나 특정하게 발생하는 빈도와 비교할 때 유용하다. 해당 패턴은 시간 복잡도가 O(n²)인 상황에서 유용하게 쓰일 수 있다. 해당 패턴을 활용하는 예시를 아래 문제에서 살펴보자.

두 개의 배열 A와 B를 받는 same이라는 함수가 있다. 이 함수는 B에 있는 값들이 A에 있는 각 값들의 제곱에 해당되면 true를 반환하고 아닌 경우에는 false를 반환한다. 각 배열에 있는 값들의 수와 빈도는 같아야 한다.

아래는 해당 문제의 입력값과 출력값의 예시이다.

same([1,2,3], [1,4,9]); // true
same([1,2,3], [1,9]); // false
same([1,2,1], [1,4,4]); // false (빈도가 같아야 함)

해결 패턴을 모르는 상태로 만들어본 same 함수이다. 짜놓고 보니 많이 미흡하다 ㅎㅎ 🤣

const same = (a, b) => {
  // a와 b 배열의 길이가 서로 맞지 않으면 이미 조건이 성립하지 않기 때문에 false를 return
  if(a.length !== b.length) return false;
  // b에 있는 숫자들이 a에 있는 숫자들의 제곱인지 확인하여 맞으면 true 아니면 false를 반환
    let tmpIndex = 0;
    // 먼저 a에 루프를 건다.    
    for (let i = 0; i < a.length; i++) {
      // a의 제곱에 해당하는 값이 b에 있는지 확인
      tmpIndex = b.indexOf(Math.pow(a[i],2));
      // b에 존재한다면 b에서 해당 값을 지워냄. 만약 없다면 false를 return.
      if(tmpIndex < 0) {
        return false;
      } else {
      	b.splice(tmpIndex, 1);
      }
    }
    
    // a가 정상적으로 다 돌았다면 true를 return.
    return true;
}

해당 접근법은 위에서 말했듯이 시간 복잡도가 O(n²)이 걸리는 순진한(?) 접근법이다. 이걸 개선시키기 위해 이제는 빈도수 세기 패턴을 적용시킬 차례이다. 위의 해결 방법에서 한 것처럼 첫 번째 배열에 루프를 적용시키고 두번째 배열에 하위 루프를 적용시켜서 각 값을 확인하는 대신에 각 배열에 한 번씩 개별적으로 루프를 적용시키는 것이다. 두 개의 루프는 두 분 중첩된 루프보다 훨씬 생산적이다. (시간 복잡도부터 n²가 아닌 2n이다)

그럼 이제 빈도수 세기 패턴을 적용시킨 코드를 보자.

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(key,2) in frequencyCounter2)) {
      return false;
    }
    if(frequencyCounter2[Math.pow(key,2)] !== frequencyCounter1[key]) {
      return false;
    }
  }
  return true;
}

앞서 배웠던 것들을 통해 우리는 배열에 비해 객체가 성능적으로 더 유리한 면들이 많다는 사실을 알고 있다. 먼저 작성된 해결법은 O(n²)의 시간 복잡도를 가지기 때문에 배열의 크기가 커지면 커질수록 결과값이 출력되는 시간값이 기하급수적으로 증가한다. 하지만 빈도수 세기 패턴이 적용된 해결방법은 O(n)의 시간 복잡도를 가져서 배열의 크기가 커져도 선형적으로 시간이 늘어날 뿐이기 때문에 앞의 해결 방법에 비해 효율이 좋다는 걸 알 수 있다.

봤듯이 빈도수 세기 패턴을 사용하는 것은 보통 객체를 활용한다. 배열이나 문자열을 분석하고 그로부터 객체를 생성하여 서로 비교하기 쉽게 만든다. 이런 식으로 코드의 성능을 크게 향상시킬 수 있는 것이다.