[Algorithm] Frequency Counters

Frequency Counters

This pattern uses objects or sets to collect values/frequencies of values. It can often avoid the need for nested loops or O(N^2) operations with arrays/strings.

예를들어, 두개의 array를 input으로 받아서, array1의 value가 array2의 squared value인지 확인하는 함수를 만들어보자.

const arr1 = [1,2,3];
const arr2 = [1,4,9];

same(arr1, arr2) // true!

예시 1

잘 작동하는 코드이다. 하지만 효율성이 떨어진다.
왜냐하면 nested loop를 사용했기 때문이다.(for loop/indexOf)
nested loop는 O(N^2)이 적용된다. 즉 array가 10개의 값을 가지고 있다면 10*10만큼 루프를 돌게된다. 10000개의 값이면 10000*10000만큼 들게된다.

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

예시 2

3개의 for loop을 사용해서 위의 코드를 개선했다. 만약 nested loop를 사용하는 것 대신, 이렇게 여러개의 loop으로 나눌 수 있다면 효율성이 올라간다. array에 10개의 값이 있다면, 3N(O(n)), 즉 3*10만큼 루프를 돈다.

• object를 활용!

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
}

예시 3

대표적인 frequency counter을 사용하는 알고리즘인 anagram이다.

function validAnagram(word1, word2) {
  if (word1.length !== word2.length) {
    return false;
  }

  let lookup = {};
  for (let i = 0; i < word1.length; i++) {
    let letter = word1[i];
    lookup[letter] = lookup[letter] ? ++lookup[letter] : 1;
  }

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

  return true;
}

validAnagram('cinema', 'iceman'); // true
validAnagram('aaz', 'zza'); // false

가능한 nested loop사용을 피하고 여러개의 loop를 사용하자 🤓