빈도수 세기 패턴

📌 빈도수 세기 패턴

빈도수 세기 패턴은 자바스크립트 객체를 사용해서 다양한 값과 빈도를 수집한다. 이 패턴은 여러 데이터와 입력값이 서로 비슷한 값으로 구성되어 있는지, 서로 간의 아나그램인지를 비교하거나 특정하게 발생하는 빈도와 비교할 때 유용하다.

👀 Example 1

• 2개의 배열을 허용하는 same이라는 함수를 만든다.
• 순서 상관 없이 첫 번째 배열의 모든 값이 제곱된 수가 두번째 배열에 포함되어 있으면 true를 반환한다. (값의 빈도는 동일)

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

Solution

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
}

for 반복문 내에서 indexOf를 사용해 중첩 루프를 사용한 풀이법이다. indexOf는 전체 배열을 잠재적으로 반복하는 것이므로 시간 복잡도는 O(n2)이다.

Refactored

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
}

이 패턴은 object나 set의 자료구조를 활용하여 빈도를 수집한다. 중첩 루프를 사용하는 대신 각 배열에 한 번씩 개별적으로 루프를 적용하므로 시간 복잡도는 O(n)이다.

👀 Example 2

• 두 문자열이 주어질 때, 두 문자열에 대해 서로 애너그램일 경우 true, 아닐경우 false를 반환한다.

애너그램이란 ? 

문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 것

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

Solution

function validAnagram(str1, str2) {
  if (str1.length !== str2.length) {
    return false;
  }
  if (str1 === str2) return true;

  let frequencyCounter1 = {};
  let frequencyCounter2 = {};

  for (let val of str1) {
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
  }
  for (let val of str2) {
    frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
  }

  for (let key in frequencyCounter1) {
    if (!(key in frequencyCounter2)) {
      return false;
    }
    if (frequencyCounter2[key] !== frequencyCounter1[key]) {
      return false;
    }
  }

  return true;
}