Frequency Counter Pattern: 빈도 카운터 패턴

Frequency Counters Pattern

빈도 카운터 패턴은 공식적인 이름은 아니다. 이 패턴은 자바스크립트의 객체를 사용해서 다양한 값과 빈도를 수집한다.

이 패턴은 알고리즘과 프로젝트에 있는 여러 데이터와 입력값이 서로 비슷한 값으로 구성되어 있는지, 값이 다른 값에 포함되는지 여부를 비교하거나, 데이터를 입력값이나 두 개 이상의 빈도 혹은 특정하게 발생하는 빈도와 비교할 때 유용하다. 이 패턴은 중첩 루프나 배열/문자열이 있는 O(N^2) 연산의 필요성을 피할 수 있다.

 

예시를 살펴보자.

2개의 배열을 허용하는 same함수를 작성하고 배열의 모든 값이 두 번째 배열에서 제곱한 해당 값을 가지면 참을 반환한다. 값의 빈도는 같아야 한다.

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

1번째 줄에서 1제곱: 1, 2제곱: 4, 3제곱: 9로 true이다. 순서는 상관없다.

2번째 줄은 2의 제곱인 4가 포함되어 있지 않기에 false이다.

3번째 줄은 빈도가 동일하지 않다. 두 번째 배열에 1이 두 개이고 4가 하나여야 한다. 

 

아래는 중첩 루프를 사용한 순진한 해결책이다.

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
}

indexOf의 기능이 중첩된 루프이기 때문에 위 접근법은 O(N^2) 즉, 제곱 시간이 사용되고 이를 순진한 접근법이라 한다. 

 

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
    }
  }
  console.log(frequencyCounter1);
  console.log(frequencyCounter2);
  
  return true
}


console.log(same([1,2,3,2], [9,1,4,4]))  // true

빈도 카운터 패턴이 사용된 코드이다. 중첩 루프가 아닌 개별적으로 루프를 적용하여 2n이 된다.

frequencyCounter가 객체를 가지는데 key는 배열의 값을 가지고, value는 빈도수를 가진다.

값을 비교하기 위해 루프를 한 번만 추가해서 둘 중 하나에만 적용하면 된다. 여기선 첫 번째 객체에 루프를 적용했다. 

console출력 내용

2를 살펴보면 2의 빈도가 2인 것을 알 수 있다. 이를 통해 다른 객체에서 4가 두 번 나타난다는 것을 알 수 있다. 3의 경우 첫 번째 객체, 즉 첫 배열에서 한번 나타난다. 두 번째 배열에선 9가 한번 나타난다. 

첫 번째 if 문에서 배열의 값의 비교가 일어나고 두 번째 if문에선 빈도를 체크하고 있다. 위 코드에선 약 3n을 가지고 있지만 단순하게 표현해서 O(n)이다.

 

 

Anagrams

아나그램이란 두 문자열이 알파벳의 나열 순서는 다르지만 알파벳 구성이 일치하면 두 단어는 아나그램이라고 한다.

한 단어를 재 배열하면 같은 단어가 된다는 것을 말한다.

ex) 가나 > 나가, 국왕 > 왕국, 남장 > 장남

ex) TAR > RAT, ARC > CAR, ELBOW > BELOW

 

두 개의 문자열이 주어졌을 때, 두 번째 문자열이 첫 번째 문자열의 아나그램인지 여부를 결정하는 함수를 작성해보자. 이 문제를 해결할 수 있는 방법이 많지만 목표는 빈도 카운터 패턴을 사용하여 해결하는 것이다.

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

 

아래는 앞서 작성한 방법대로 작성한 예시이다.

function validAnagram(str1, str2) {
  if(str1.length !== str2.length) {
    return false
  }
  
  let freCounter1 = {};
  let freCounter2 = {};
  
  for(let val of str1) {
    freCounter1[val] = (freCounter1[val] || 0) +1
  }
    for(let val of str2) {
    freCounter2[val] = (freCounter2[val] || 0) +1
  }
  
  for(let key in freCounter1) {
    if(!(key in freCounter2)) {
      return false
    }
    if(freCounter1[key] !== freCounter2[key]) {
      return false
    }
  }
  return true
}

 

이번에는 조금 다른 구조로 작성한 예시를 보자. O(n)

function validAnagram(first, second) {
  if(first.length !== second.length) {
    return false
  }
  const lookup = {};
  
  for(let i =0; i < second.length; i++) {
    let letter = first[i];
    
    // if letter exists, increment, otherwise set to 1
    lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
  }
  
  for(let i =0; i < second.length; i++) {
    let letter = second[i]
    // can't find letter or ltter is zero ten it's not anagram
    if(!lookup[letter]) {
      return false;
    } else {
      lookup[letter] -= 1;
    }
  }
  return true;
}

이 패턴은 여러 데이터가 있어서 서로 비교해야 하는 경우, 특히 데이터가 같은 개별 데이터 조각으로 구성되어 있는지, 한 배열이 각 개별 데이터 조각을 제곱한 다른 배열과 같은지, 또는 내가 본 다른 것과 같은지를 확인해야 하는 경우, 숫자가 같은 숫자로만 구성되어 있고 순서는 다른지를 확인해야 하는 경우 등 다양한 방식으로 이 패턴을 응용할 수 있다.