알고리즘

[알고리즘] 빈도 카운터 (Frequency Counter)

_doit 2024. 8. 29. 19:09
728x90
반응형

빈도 카운터 (Frequency Counter)란?

빈도 카운터는 배열이나 문자열에서 각 요소나 문자의 빈도(몇 번 나오는지)를 세는 방법이다.

알고리즘에서 빈도 카운터 패턴(Frequency Counter Pattern)은 객체(Object)나 Set과 같은 자료구조를 사용하여 배열이나 문자열 내의 값들의 빈도(즉, 특정 값이 몇 번 등장하는지)를 수집하고 이를 비교하는 방법이다. 이 패턴은 중첩된 루프나 O(N^2)와 같은 비효율적인 연산을 피하는 데 매우 유용하다

 

빈도 카운터는 보통 객체를 사용

자바스크립트에서 보통 객체를 사용하여 이러한 빈도 카운터를 만든다. 객체는 key-value 쌍으로 데이터를 저장하므로, 특정 요소를 key로, 그 요소의 빈도를 value로 저장할 수 있다.

예를 들어, 배열 [1, 2, 2, 3, 3, 3]의 빈도를 계산해봅시다

let frequencyCounter = {};
let arr = [1, 2, 2, 3, 3, 3];

for (let num of arr) {
    frequencyCounter[num] = (frequencyCounter[num] || 0) + 1;
}

이 코드는 frequencyCounter 객체를 다음과 같이 만든다

{
    1: 1,  // 1은 1번 등장
    2: 2,  // 2는 2번 등장
    3: 3   // 3은 3번 등장
}

 

 

빈도 카운터 패턴 예시 문제 

  • 함수 이름: same
  • 목표: 첫 번째 배열의 각 값의 제곱이 두 번째 배열에 동일한 빈도로 존재하는지 확인합니다.
  • 입력: 두 개의 배열 (arr1, arr2)
  • 출력: 첫 번째 배열의 모든 값의 제곱이 두 번째 배열에 같은 빈도로 존재하면 true, 그렇지 않으면 false를 반환.
same([1,2,3], [4,1,9]) // true
same([1,2,3], [1,9]) // false
same([1,2,1], [4,4,1]) // false (must be same frequency)

 

 

1. A Naive Solution

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;
}

Time Complexity: N^2

이 코드는 첫 번째 배열의 각 요소를 기준으로 다시 배열 전체를 탐색하여 해당 요소가 몇 번 등장했는지 확인한다. 이 과정은 매우 비효율적이며, 배열의 길이가 n일 때, 시간 복잡도가 O(n^2)이 된다

2. refactored

빈도 카운터: 두 배열의 각 요소의 빈도를 계산하는 두 개의 빈도 카운터(객체)를 만든다.

function 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 (!(key ** 2 in frequencyCounter2)) {
            return false;
        }
        if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
            return false;
        }
    }

    return true;
}

Time Complexity: O(n)

반면, 빈도 카운터를 사용한 방법은 배열을 한 번만 순회하면서 각 요소의 빈도를 계산하므로 시간 복잡도는 O(n)이 된다

따라서 각각의 두 개의 루프가 두개의 중첩된 개별 루프보다 훨씬 낫다

 

결론

빈도 카운터 패턴은 배열이나 문자열에서 각 요소의 빈도를 효율적으로 계산하고 이를 활용해 다양한 문제를 해결하는 데 유용한 알고리즘 패턴이다. 중첩된 루프를 사용하여 비효율적으로 문제를 해결하기보다는, 빈도 카운터를 사용하여 시간 복잡도를 크게 줄일 수 있다. 이 패턴을 잘 이해하고 활용하면, 복잡한 문제도 효과적으로 해결할 수 있다.

 

728x90
반응형