[Algorithm] 알고리즘 기본 패턴 1 - Frequency Counter (빈도수 세기)

 

1. Frequency Counter (빈도수 세기)

 

배열/ 문자열의 요소들의 빈도수를 비교할 때 사용하며

이 패턴은 Object 또는 Set을 사용하여 값의 값/빈도를 수집합니다

중첩 루프 또는 O(N^2) 중첩 루프를 O(n)으로 최적화 해야 합니다

 

 

예 1)

두 개의 배열을 인수로 받는 same이라는 함수가 있습니다. 

이 함수는 배열의 모든 값이 두 번째 인수 배열에 해당하는 값의 제곱을 갖는 경우 참을 반환해야 합니다. 

값의 빈도는 동일해야 합니다.

 

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

 

이전 사용했던 풀이법은 아래와 같습니다.

const same = (arr1, arr2) =>{
    // 1️⃣ 길이 비교: O(1)
    if(arr1.length !== arr2.length) return false
    
    // 2️⃣ 정렬: O(n log n)
    let a1 = arr1.sort((a,b) => a-b)
    let a2 = arr2.sort((a,b) => a-b)
    
    // 3️⃣ map, join 작업: O(n)
    return a1.map(n => n**2).join('') === a2.join('')
}

 

참고로 V8 v7.0 이후 QuickSort -> TimSort 로 변경되며 

최대시간 복잡도가 O(N^2) -> O(N log N) 으로 향상 되었습니다.

https://v8.dev/blog/array-sort

Getting things sorted in V8 · V8

 

Frequency Counter 패턴 적용 코드

 

배열의 모든 값이 두 번째 인수 배열에 해당하는 값의 제곱을 갖는 경우 참을 반환해야 한다

const same = (arr1, arr2) => {
    // 1. 길이가 다르면 바로 false 반환
    if(arr1.length !== arr2.length) return false;
    
    // 2. 각 배열의 요소 빈도수를 저장할 객체들
    const counter1 = {};
    const counter2 = {};
    
    // 3. 한번의 순회로 두 배열의 빈도수를 동시에 계산
    for(let i = 0; i < arr1.length; i++) {
        counter1[arr1[i]] = (counter1[arr1[i]] || 0) + 1;
        counter2[arr2[i]] = (counter2[arr2[i]] || 0) + 1;
    }
    
    // 4. arr1의 각 요소의 제곱이 arr2에 있는지 확인
    for(let key in counter1) {
    	// 여기서 필요한 조건으로 비교합니다
        // 제곱한 값이 arr2에 없거나 빈도수가 다르면 false
        if(counter2[key ** 2] !== counter1[key]) return false;
    }
    
    return true;
}

 

 

예 2)

 

두 개의 문자열이 주어졌을 때, 두 번째 문자열이 첫 번째 문자열의 아나그램인지 확인하는 함수를 작성합니다.

아나그램은 다른 글자의 글자를 재배열하여 형성된 단어, 구 또는 이름입니다

(예: cinema 는 iceman 으로 만들어짐).

 

validAnagram('', '') // true
validAnagram('aaz', 'zza') // false
validAnagram('anagram', 'nagaram') // true
validAnagram("rat","car") // false
validAnagram('awesome', 'awesom') // false
validAnagram('qwerty', 'qeywrt') // true
validAnagram('texttwisttime', 'timetwisttext') // true

 

 

const validAnagram = (str1, str2) => {
    if(str1.length !== str2.length) return false;
    
    const counter1 = {};
    const counter2 = {};
    
 
    for(let i = 0; i < str1.length; i++) {
        counter1[str1[i]] = (counter1[str1[i]] || 0) + 1;
        counter2[str2[i]] = (counter2[str2[i]] || 0) + 1;
    }
    
  
    for(let key in counter1) {
       if(counter2[key] !== counter1[key]) return false;
    }
    
    return true;
}

 

 

 

 

다음 알아볼 패턴들..

Multiple Pointers (다중 포인터)  https://daunje0.tistory.com/191
Sliding Window https://daunje0.tistory.com/262
Divide and Conquer https://daunje0.tistory.com/263
Dynamic Programming
Greedy Algorithms
Backtracking