[알고리즘]FrequencyCounter - 빈도수 세기

두 배열을 받는 함수 same은 arr2 배열의 요소가 arr1 배열의 요소의 제곱이면 true 아니면 false를 리턴한다.
ex) same([1, 2, 1, 3], [1, 1, 4, 9]) => true
same([1, 2, 1, 3], [1, 4, 1, 8]) => false

1. 배열을 for 루프로 반복하면서 해당 요소를 다른 배열에 indexOf를 활용하여 찾는 방법

function same(arr1, arr2) {
    if(arr1.length !== arr2.length) return false
    for(let i = 0; i < arr1.length; i++){
        let corretIndex = arr2.indexOf(arr1[i] ** 2)
        if(corretIndex === -1) return false
        console.log(arr2)
        arr2.splice(corretIndex, 1)
    }
    return true
}

루프로 배열을 돌고 indexOf로 또 배열을 돌기 때문에 O(n^2)의 복잡성을 가진다.
배열의 길이가 1000일때 최대 1000000번..

2.객체를 이용하여 해당 수의 빈도수를 체크하고 두 객체의 키를 이용해서 비교하는 방법

function same(arr1, arr2) {
    if(arr1.length !== arr2.length) return false
    
    let frequencyCounter1 = {}
    let frequencyCounter2 = {}
    for (let el of arr1){
        frequencyCounter1[el] = (frequencyCounter1[el] || 0) + 1
    }
    for (let el of arr2){
        frequencyCounter2[el] = (frequencyCounter2[el] || 0) + 1
    }

    console.log(frequencyCounter1)
    console.log(frequencyCounter2)
    
    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter1[key] !== frequencyCounter2[key ** 2]){
            return false
        }
    }
    return true
}

이 방법엔 배열의 전체 크기에 걸쳐 세 개의 루프가 있다.
=> 3n의 복잡도를 갖고 있기 때문에 O(n)의 복잡성으로 단순화할 수 있다.

---

위 내용을 학습한 후 아래 문제를 풀어보았다.

내가 해결한 방법

function validAnagram(str1, str2) {
    if(str1.length !== str2.length) return false
    
    let anagram1 = {}
    let anagram2 = {}
    
    for(let i = 0; i < str1.length; i++){
        anagram1[str1[i]] = (anagram1[str1[i]] || 0) + 1 
    }
    for(let i = 0; i < str2.length; i++){
        anagram2[str2[i]] = (anagram2[str2[i]] || 0) + 1 
    }

    for(let key in anagram1){
        if(!(key in anagram2)){
            return false
        }
        if(anagram1[key] !== anagram2[key]){
            return false
        }
    }
    return true
}

강의에서 해결한 방법

function validAnagram(str1, str2) {
    if(str1.length !== str2.length) return false
    
    let anagram = {}
    
    for(let i = 0; i < str1.length; i++){
        let letter = str1[i]
        anagram[letter] ? anagram[letter] + 1 : anagram[letter] = 1;
    }

    for(let i = 0; i < str2.length; i++){
        let letter = str2[i]
        if(!anagram[letter]){
            return false
        } else {
            anagram[letter] -= 1;
        }
    }
    return true
}

내가 직접 풀어본 것은 학습내용을 바탕으로 동일하게 생각해서 객체를 두개 생성해서 빈도수를 체크했지만 강의에서 해결한 방법은 첫 예제처럼 제곱근을 이용하는게 아닌 알파벳이기 때문에 한 개의 객체로 빈도수를 체크하고 그 객체의 키를 이용해 있는지 없는지만 판별해주면 되는 방법으로 문제를 해결했다.