문제 해결 패턴 - Frequency Counters

Frequency Counters 는 실제로 빈도 카운터라고 불리지 않음. (공식 이름도 없음)

 

이 패턴은 보통 js의 객체를 사용해서 다양한 값과 빈도를 수집한다.

 

Tip : 가능한 중첩된 루프는 사용하지 않는 것이 좋다. 두 개의 루프가 두 개의 중첩된 개별 루프보다 훨씬 낫다. (n^2 < n)

 

Frequency Counters는 보통 객체를 사용한다.

 

배열이나 문자열의 내용을 분석하여 비교할때는

두 개의 배열을 객체로 세분화하여 각 배열의 요소들을 분류한 다음

각 배열을 비교하는 것이 좋다.

 

O(n^2) => indexOf 가 중첩된 배열의 역할을 한다.

 

 

 

O(n)

 

 

둘 다 같은 결과를 내지만 시간복잡도 측면에서 봤을때는 후자가 훨씬 성능이 좋다.

전자는 for문 안에서 indexOf을 사용하여 O(n^2) 이 되지만,

후자는 for문을 3번 반복하여 3n. 즉 O(n) 이기 때문이다.

 

 

 

+ 위 자료에서는 for문을 3번 써서 O(n)으로 해결했지만, for문을 2번만 써서 O(n) 으로도 해결할 수 있다.

 

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

 

 

본 내용은 작성자가 (Udemy) JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 듣고 정리 및 메모한 내용입니다.  오역 및 오개념이 있을 수 있으니 바로잡기 위해 문제가 있는 경우 댓글 남겨주시면 매우 감사하겠습니다.

https://www.udemy.com/course/best-javascript-data-structures/

JavaScript (JS) Algorithms and Data Structures Masterclass