230829 - Frequency Counter (빈도 카운터) 패턴

오늘 내가 배운 것

1. Frequency Counter

2.  두 가지 배열이 주어졌을 때 첫 번째 배열의 각 요소가 두 번째 배열에 있는지 확인하기

3. 시간 복잡도 VS 공간 복잡도

---

 

1. Frequency Counter

데이터의 빈도수를 계산하기 위한 알고리즘 패턴
배열이나 문자열 등의 자료구조에서 특정 요소가 몇 개 있는지 셀 때 주로 사용된다.

// [1,2,1,3]
{
    "1": 2,
    "2": 1,
    "3": 1
}

키는 배열의 요소, 값은 해당 요소의 빈도수이다.

주로 사용하는 상황

• 1. 두 개의 배열이나 문자열이 같은 요소로 이루어져 있는지 확인하기
• 2. 배열이나 문자열에서 특정 요소의 빈도수를 찾기
• 3. 데이터의 분포를 빠르게 파악하기

등...

 

2.  두가지 배열이 주어졌을 때 첫 번째 배열의 각 요소가 두 번째 배열에 있는지 확인

방법 1

1번 배열의 제곱과 2번 배열이 맞는지 반복문을 통해서 검증한다.

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
}

console.log(same([1, 2, 3], [4, 1, 9])) // true
// console.log(same([1, 2, 3], [4, 1, 4])) // false
// console.log(same([1, 2, 3], [4, 1, 9, 4])) // false

이 방법은 시간 복잡도가 O(n^2)이다. for문을 1번밖에 사용하지 않았지만 indexOf()가 내부적으로 반복문을 사용하기 때문에 O(n^2)이다.

방법 2

빈도 카운터 패턴을 이용하는 방법

function same2(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
}

console.log(same2([1, 2, 3], [4, 1, 9])) // true
// console.log(same2([1, 2, 3], [4, 1, 4])) // false

두 개의 루프를 이용해서 시간이 오래 걸릴 거라 생각했지만 중첩이 아니기 때문에 3n 일 뿐이다 - 두 개의 루프가 하나의 중첩 루프보다 효율적이다

위의 same2는 O(3n)이지만 빅오 표기법은 O(n)로 표현한다.

 

 

3. 시간 복잡도 VS 공간 복잡도

위의 빅오 표기법은 시간 복잡도에 대한 표현이었다.
방법 1과 2의 공간 복잡도를 보면 각각 O(1), O(n)이다.

그래서 생기는 궁금증은

same은 O(1) 공간복잡도이고, O(n^2) 시간 복잡도이고,
same2는 O(n) 공간복잡도이고, O(n) 시간 복잡도이다

그러면 뭐가 더 효율적일까?

 

이런 문제는 로직을 사용하는 자원(시간, 공간)에 따라 달라지는 문제이다.

이거여서 좋다, 저거여서 좋다 보다는 처리를 빨리해서 값을 보여줘야 하는 경우에는 시간 복잡도가 더 효율적인 로직을 이용해야 하고, 한정되어 있는 메모리를 이용해야 하는 경우에는 공간 복잡도가 효율적인 것이 필요하다.

그래서 상황을 잘 고려한 로직이 필요할 것 같다.

 

---