본 포스팅은 깃헙 블로그 사용 당시 작성한 포스팅입니다.
Frequency Counter (빈도 카운터)
자바스크립트 객체를 사용해서 다양한 값과 빈도를 수집하는 것
여러 데이터 사이 (혹은 입력값과 데이터 사이에) 서로 비슷한 값으로 구성되어 있는 지, 서로 아나그램₁으로(하단부 참조) 구성되어있는지 등 두 개 이상의 빈도 혹은 특정하게 발생하는 빈도를 비교할 때 유용하다
중첩된 루프를 사용해 O(n²)의 시간 복잡도를 가지거나, indexOf()메소드와 같이 중첩된 루프를 내포한 메소드에 비해 O(n)의 시간복잡도를 가지게 되므로 계산시간이 더 빠르다.
예시
문제 내용
두개의 배열을 입력받아 arr2가 arr1의 요소들을 제곱한 값으로 배열되어있는 지(순서는 무관) 확인할 수 있는 함수를 만드세요.
중첩된 루프를 사용한 해결
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| function checkedSame(arr1, arr2){ if(arr1.length !== arr2.length){ return false } for(let i = 0; i < arr1.length; i++){ let check = arr2.indexOf(arr1[i] ** 2) if(check === -1){ return false } arr2.splice(check, 1) } return true }
|
빈도 카운터 (Frequency Counter)를 이용해 해결
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| function checkedSame(arr1, arr2){ if(arr1.length !== arr2.length){ return false } let frequencyCounter1 = {} let frequencyCounter2 = {} for(let value of arr1){ frequencyCounter1[value] = (frequencyCounter1[value] || 0) + 1 } for(let value of arr2){ frequencyCounter2[value] = (frequencyCounter1[value] || 0) + 1 } for(let key in frequencyCounter1){ if(!(key ** 2 in frequencyCounter2)){ return false } if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){ return false } } return true }
|
빈도 카운터는 보통 객체를 사용한다. 배열이나 문자열의 내용을 분석하는 것으로 선형 구조를 가지며 해당 분석은 문자열이나 배열에서 생성된 다른 객체의 형태와 신속하게 비교할 수 있다
아나그램(anagram)₁ 이란 두 문자열의 배치(나열 순서)는 다르지만 알파벳 구성이 일치하는 경우를 말한다.