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

빈도수 세기(Frequency Counter) 패턴이란?

빈도수 세기(Frequency Counter) 패턴은 중첩 반복문 없이, 배열이나 문자열 등의 값의 발생 빈도를 객체에 저장해두고 그 정보를 기반으로 문제를 해결하는 방식이다.
이 패턴은 시간 복잡도를 O(n²)에서 O(n)으로 줄일 수 있기 때문에 유용하다.

---

🔍 예시 문제

배열 arr1과 arr2가 있을 때, arr2가 arr1의 각 원소를 제곱한 값들을 같은 빈도로 포함하고 있는지 확인하는 함수를 만들어보자.

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

빈도수 세기 패턴을 적용하지 않았을 때 O(n²)

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

  for (let i = 0; i < arr1.length; i++) {
    // indexOf*로 제곱값 찾기 (O(n))
    let correctIndex = arr2.indexOf(arr1[i] ** 2); // (2)
    if (correctIndex === -1) return false;

    // 찾은 요소 제거
    arr2.splice(correctIndex, 1); // (3)
  }
  return true; // (4)
}

1. 먼저 두 배열의 길이를 비교해 다르면 바로 false를 반환한다.
2. arr1의 각 원소를 제곱한 값을 arr2에서 indexOf로 찾는다.
3. 찾지 못하면 false, 찾았다면 그 값을 splice로 배열에서 제거한다.
4. 이 과정을 반복해 모든 값이 일치하면 true를 반환한다.

⚠️ 문제점

indexOf* 는 내부적으로 배열을 매번 순회하는 메서드 → O(n²) 성능을 야기함

indexOf() 메서드는 호출한 스트링 객체나 배열에서 주어진 값과 일치하는 값 혹은 요소의 첫 번째 인덱스를 반환하고 존재하지 않으면 -1을 반환한다.

---

빈도수 세기 패턴을 적용했을 때 O(n)

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

  // 1. 빈도수 객체 생성
  const frequencyCounter1 = {};
  const frequencyCounter2 = {};

  // 2. arr1의 요소 빈도수 카운트
  for (let val of arr1) {
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
  }

  // 3. arr2의 요소 빈도수 카운트
  for (let val of arr2) {
    frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
  }

  // 4. 빈도수 비교
  for (let key in frequencyCounter1) {
    // 4-1. 제곱값 존재 여부 확인
    if (!(key ** 2 in frequencyCounter2)) {
      return false;
    }
    // 4-2. 빈도수 일치 여부 확인
    if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
      return false;
    }
  }

  return true;
}

1. 배열의 길이가 다르면 false를 반환한다.
2. arr1의 각 값을 키(key)로 하여 몇 번 나왔는지 frequencyCounter1 객체에 기록한다.
3. 같은 방식으로 arr2도 frequencyCounter2에 기록한다.
4. arr1의 각 키를 기준으로, 해당 키의 제곱이 arr2에서 존재하는지 확인한다.*
5. 값이 존재하더라도 등장 횟수가 다르면 false를 반환한다.
6. 위 조건을 모두 통과하면 true를 반환한다.

*객체(Object)는 해시 테이블(Hash Table) 구조로 구현되어 있다.

- 자바스크립트에서 객체의 키는 내부적으로 해시화된다.
- 따라서 특정 키가 있는지 찾을 때, 해시값을 통해 즉시 접근이 가능하다.
- 해시 테이블에서 키를 찾는 연산은 평균적으로 O(1)이다.

✅ 장점

각 배열을 한 번씩만 순회한다 → 시간 복잡도 O(n)