Frequency Counter(빈도 카운터)_posted by 2022

Soye Park·2022년 11월 1일
0

깃헙블로그백업

목록 보기
3/10
post-thumbnail

본 포스팅은 깃헙 블로그 사용 당시 작성한 포스팅입니다.

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){
// 조건 중 가장 파악이 쉬운 배열길이로 1차적으로 선별
if(arr1.length !== arr2.length){
return false
}
for(let i = 0; i < arr1.length; i++){
// indexOf 메소드를 활용해 arr1[i]의 제곱이 맞는 지 각 요소별로 확인
let check = arr2.indexOf(arr1[i] ** 2)
// 만약 indexOf 값이 -1이 나온다면 일치하지 않는다는 의미이므로 false를 리턴
if(check === -1){
return false
}
//arr2 에서 확인된 요소들을 하나씩 제거 (과정확인)
arr2.splice(check, 1)
}
// 위 반복문을 무사히 통과했다면 true
return true
}

// 위 방식의 경우 O(n^2)만큼의 시간복잡도를 가진다. 왜냐면 for문과 indexOf() 메소드 사용으로 반복문이 중첩되어있는 상태이기 때문이다. 이 때문에 배열의 길이가 늘어나면 시간 복잡도가 빠르게 상승한다.

빈도 카운터 (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){
// 위 방법과 동일하게 가장 파악이 쉬운 배열길이로 1차적 선별
if(arr1.length !== arr2.length){
return false
}
// 각 배열이 위치할 빈 객체 생성
let frequencyCounter1 = {}
let frequencyCounter2 = {}
// for of 문이므로 배별의 값에 따라 반복된다.
// value값으로 key가 추가되고, 있다면 1을, 동일요소가 더 있다면 +1씩을 추가한다.
for(let value of arr1){
frequencyCounter1[value] = (frequencyCounter1[value] || 0) + 1
}
for(let value of arr2){
frequencyCounter2[value] = (frequencyCounter1[value] || 0) + 1
}
//for in 문은 인덱스 기반으로 배열 요소를 꺼내 사용한다.
for(let key in frequencyCounter1){
// 불러들인 frequencyCounter1의 key값의 제곱이 frequencyCounter2 의 키값과 동일하지 않으면 false를 리턴
if(!(key ** 2 in frequencyCounter2)){
return false
}
if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
return false
}
}
return true
}

// 위 방식으로 접근하게되면, 중첩 없이 반복문이 쓰여지므로 반복문 갯수 * n의 시간복잡도를 가진다. 하지만 일반적으로 앞을 정리하고 O(n)만큼의 시간복잡도를 가진다고 얘기한다.

빈도 카운터는 보통 객체를 사용한다. 배열이나 문자열의 내용을 분석하는 것으로 선형 구조를 가지며 해당 분석은 문자열이나 배열에서 생성된 다른 객체의 형태와 신속하게 비교할 수 있다


아나그램(anagram)₁ 이란 두 문자열의 배치(나열 순서)는 다르지만 알파벳 구성이 일치하는 경우를 말한다.

profile
응애FE개발자/ 블로그 이전 : https://soyeah-log.vercel.app/

0개의 댓글