[Udemy] Frequency Counter(빈도수 세기) 패턴 파악하기

오늘은 문자열, 배열과 같은 선형구조의 자료구조에서 빈도수 세기 패턴에 대해 알아보자.

문제

두 배열이 주어졌을 때, 첫번째 배열의 각 요소의 제곱수가 두번째 배열이 있는지 확인하는 함수를 작성하라.

 

input: [1,2,3], [4,1,9]
output: true

• 순서는 상관없이 첫번째 배열의 각 요소의 제곱수가 모두 2번째 배열에 있으므로 true

input: [1,2,3], [1,9]
output: false

• 2의 제곱수인 4가 2번째 배열에 없으므로 false

input: [1,2,2], [1,1,4]
output: false

• 첫번째 배열에는 1이 1개, 2가 2개인데 두번째 배열에서는 1의 제곱수가 2개, 2의 제곱수가 1개이므로 빈도가 다르므로 false

일반적인 접근

function frequencyValues(arr1, arr2) {
    const copiedArr2 = [...arr2];

    arr1.forEach((num) => {
        const squaredNum = num*num;
        const findedIndex = copiedArr2.findIndex(num => num === squaredNum)

        if (findedIndex === -1) {
            copiedArr2.push(squaredNum)
        } else {
            copiedArr2.splice(findedIndex,1)
        }
    })

    return copiedArr2.length === 0;
}

일반적인 접근 방법으로는 첫번째 배열의 요소를 가지고 제곱한 값이 두번째 배열 요소에 존재하는지 찾고,
만약 존재한다면 splice 메서드로 제거하고 결과값을 비교하는 방식으로 구현한다.

 

위 방법은 중첩 반복문이 있어 시간복잡도 O(n^2)의 방식이다.

만약 두 배열의 길이가 1000개 일 경우, 1,000,000 회 연산이 수행되어 연산이 오래걸린다.

객체를 사용한 접근법

function frequencyCount(arr1, arr2) {
    if (arr1.length !== arr2.length) {
        return false;
    }
    const frequencyObj1 = {}
    const frequencyObj2 = {}

    for (let num1 of arr1) {
        frequencyObj1[num1] = (frequencyObj1[num1] || 0) + 1
    }
    for (let num2 of arr2) {
        frequencyObj2[num2] = (frequencyObj2[num2] || 0) + 1
    }

    for (let num1 in frequencyObj1) {
        if (!((num1 ** 2) in frequencyObj2)) {
            return false;
        }
        if (frequencyObj1[num1] !== frequencyObj2[num1 ** 2]) {
            return false;
        }
    }
    return true;
}

우선 위 코드의 시간복잡도는 중첩된 반복문이 없기 때문에 O(n)을 가진다.

 

첫번째 배열과 두번째 배열의 각 요소의 빈도수를 담고 있는 객체를 생성한다.
그 후 첫번째 객체를 순회하여 key 값을 가지고 두번째 객체값의 key값과 빈도수 값을 나타내는 value값을 비교한다.

 

이는 반복문 1회만으로 모두 해결할 수 있기 때문에 매우 시간 복잡도를 줄일 수 있는 좋은 접근 방법이다.

앞으로 선형 자료구조의 빈도수 세기 문제 패턴에 대해서 위와 같이 객체를 활용한 방식을 떠올려 시간복잡도를 줄여보자.

참조

• Udemy JavaScript 알고리즘 & 자료구조 강의
• https://www.udemy.com/course/best-javascript-data-structures/learn/lecture/28559703#overview