서론
오늘 이야기할 주제는 빈도카운터 패턴(Frequence Counter Pattern)이다.
빈도카운터 패턴은 욕심법, 슬라이딩 윈도우 처럼 공식이름을 가진 패턴은 아니다. 내가 보는 강의에서 강의자가 붙인 이름으로 비공식이지만 많이 쓰이는 패턴 중 하나이다.
본론
그래서 빈도카운터 패턴이 무엇인가?
두 개의 배열이 주어졌을때 그 배열이 조건에 맞아떨어지는지를 체크하는 것이 빈도 카운터 패턴이다.
예시1
두 개의 배열이 주어졌을때 하나의 두번째 배열은 첫번째 배열의 제곱이다.
이때 배열의 순서는 정렬되어있지 않아도 괜찮으며, 오로지 배열의 제곱이 존재하며 일치하는지만을 판단하면 된다. 이 문제를 푸는 방법에는 간단하게 for을 이용해서 서로 비교하는 방법이 있다.
function validAnagram(arr1, arr2){
if(arr1.length !== arr2.length) {return false;}
var validCheckArray1 = {};
var validCheckArray2 = {};
//배열 정렬
for(let val of arr1){
validCheckArray1[val] = (validCheckArray1[val] || 0) + 1
}
//배열 정렬
for(let val of arr2){
validCheckArray2[val] = (validCheckArray2[val] || 0) + 1
}
//확인
for(key of validCheckArray1){
//**은 제곱을 나타냅니다.
if(!(key ** 2 in validCheckArray2)) {return false;}
if(validCheckArray2[key ** 2] !== validCheckArray1[key]) {return false;}
}
return true;
}다른 방법으로 for문 안에 for문을 또 실행하거나 indexOf를 사용해서 구별하는 방법도 있다. 하지만 중첩된 배열보다 이렇게 연속해서 루프문을 사용하는게 더 낫다. 그 이유는 시간 복잡도 때문이다. 내부에서 한 번 더 for루프를 돌리거나 indexOf를 사용하면 시간 복잡도는 O(n^2)이 된다. 반면에 이렇게 연속해서 루프를 사용하면 O(2n)이 된다. 이건 O(n)으로 간소화 할 수 있다. 더 길 지언정 훨씬 효율적인 것이다.
예시2
Frequency Counter - validAnagram
Given two strings, write a function to determine if the second string is an anagram of the first. An anagram is a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.
Examples: validAnagram('', '') // true validAnagram('aaz', 'zza') // false validAnagram('anagram', 'nagaram') // true validAnagram("rat","car") // false) // false validAnagram('awesome', 'awesom') // false validAnagram('amanaplanacanalpanama', 'acanalmanplanpamana') // false validAnagram('qwerty', 'qeywrt') // true validAnagram('texttwisttime', 'timetwisttext') // true Note: You may assume the string contains only lowercase alphabets. Time Complexity - O(n)
위의 두번째 예시는 내일 자세하게 풀이하고자 한다.
이전 게시글에서도 다루었던 완주하지 못한 선수에서도 이 패턴을 사용할 수 있다. participant와 completion의 두 배열이 주어졌을때 둘이 다른 요소를 찾아내면 되기 때문이다. 다들 이 패턴을 적용해서 한 번 다시 풀어보길 바란다.
완주하지 못한 선수
validarity : 100%
language : javascript
link : 코딩 테스트 고득점 kit > 해시 > 완주하지 못한 선수
참고
