[algorithm] Frequency Counter 패턴 (빈도수 카운터 패턴)

Frequency Counter 패턴이란?

Frequency Counter 패턴은 일반적인 알고리즘 패턴 중 하나로, 두 배열이나 문자열이 동일한 구성 요소를 가지고 있는지를 판단할 때 유용하다. 이 패턴은 객체나 집합(Set)을 사용하여 배열이나 문자열의 값을 수집하고, 그 값들의 빈도를 기록하여, 두 배열 또는 문자열이 동일한 구성 요소를 가지고 있는지 비교한다.

이 패턴을 이용하면, 중첩 반복문이나 O(N^2) 시간 복잡도의 연산을 피할 수 있어 성능을 향상 시킬 수 있다.

 

이 패턴은 특히 배열이나 문자열이 같은 요소나 구조를 가지는지, 혹은 아나그램인지 등을 확인하는 문제에서 강력한 도구로 활용된다.

 

Frequency Counter 패턴 예시

 

예시 1: 두 배열이 서로 제곱 관계인지 확인하는 함수

 

문제
두 배열을 입력으로 받아, 두 번째 배열이 첫 번째 배열의 각 요소의 제곱으로 구성되어 있는지를 확인하는 함수를 작성하라.
여기서 각 요소들의 빈도 또한 동일해야 한다.

 

코드

function same(arr1, arr2) {
		if (arr1.length !== arr2.length) {
				return false;
		}
		arrFrequency1 = {};
		arrFrequency2 = {};
		for (let value of arr1) {
				arrFrequency1[value] ? arrFrequency1[value] += 1 : arrFrequency1[value] = 1;
		}
		for (let value of arr2) {
				arrFrequency2[value] ? arrFrequency2[value] += 1 : arrFrequency2[value] = 1;
		}
		for (let key in arrFrequency1) {
				if (!(key ** 2 in arrFrequency2)) {
						return false;
				}
				if (arrFrequency1[key] !== arrFrequency2[key**2]){
						return false;
				}
		}
		return true;
}


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

 

예시 2: 아나그램 판별 함수

 

두 문자열이 주어졌을 때, 하나의 문자열을 재배열하여 다른 문자열을 만들 수 있는지 여부를 확인하는 함수를 작성하라.

 

코드

function validAnagram (str1, str2) {
		// 1. 각 문자열의 길이를 비교하여, 다르면 false 반환
		if (str1.length !== str2.length) {
				return false;
		}
		// 2. 빈도수 객체 정의
		let str1Frequency = {};
		// 3. str1의 빈도를 객체로 정리
		for (let value of str1) {
				str1Frequency[value] ? str1Frequency[value] += 1 : str1Frequency[value] = 1;
		}
		// 4. str2의 각 요소들을 가져오는 반복문 수행
		for (let value of str2) {
				// 5. 빈도수 객체의 키 중 해당 요소가 없다면 false 반환
				if (!str1Frequency[value]) {
						return false;
				}
				// 6. 빈도수 객체의 키 중 해당 요소가 있다면 해당 키의 값에서 -1 
				else {
						str1Frequency[value] -= 1;
				}
		}
		// 7. 통과했다면, true 반환
		return true;
}

console.log(validAnagram('', ''));
console.log(validAnagram('aaz', 'zza'));
console.log(validAnagram('anagram', 'nagaram'));
console.log(validAnagram('rat', 'car'));
console.log(validAnagram('awesome', 'awesom'));
console.log(validAnagram('qwerty', 'qeywrt'));
console.log(validAnagram('texttwisttime', 'timetwisttext'));