[알고리즘] javascript 문제해결 패턴 - frequency counter(빈도 카운터)

✅ frequency counter(빈도 카운터)란?

주어진 배열 속 요소의 빈도를 확인하는 문제

• worst : 중첩 for문
• best : 객체 사용

의사코드

A배열의 각 요소의 제곱이 B요소에 포함되었는지 확인하시오 (갯수도 같아야 함)

👍best

시간 복잡도 : O(n)

A 순회해서 {요소: 개수, ...} 객체 만듬 
B 순회해서 {요소: 개수, ...} 객체 만듬 
A객체의 key 순회해서 B객체 값과 비교 
  같지 않으면 return false 
  순회 마쳤으면 return true

👎worst

시간 복잡도 : O(n^2)

for A 순회 
  B.indexOf(n) 찾아서 삭제 
  없으면 return false 
  순회 마쳤으면 return true

문제 풀이

1. 주어진 두 숫자가 같은 숫자, 같은 빈도를 가지고 있는지 확인하는 함수를 작성하시오.

   function sameFrequency(a,b){
   a = a.toString();
   b = b.toString();
   
   if(a.length !== b.length) return false;
   
   let objA = {};
   let objB = {};
   
   for(let i = 0; i < a.length; i++) {
    objA[a[i]] = (objA[a[i]] || 0) + 1; 
   }
   
   for(let i = 0; i < b.length; i++) {
    objB[b[i]] = (objB[b[i]] || 0) + 1; 
   }
   
   for(let key in objA) {
      if(objA[key] !== objB[key]) return false;
   }
   return true;
   }

2. 배열 안의 중복 여부를 확인하는 함수를 작성하시오.

   function areThereDuplicates(...args) {
   let obj = {};
   for(let i = 0; i < args.length; i++) {
    if(obj[args[i]]) return true;
    else obj[args[i]] = 1;
   }
   return false;
   }

   • 다중포인터 사용

     function areThereDuplicates(...args) {
     // Two pointers
     args.sort((a,b) => a > b);
     let start = 0;
     let next = 1;
     while(next < args.length){
     if(args[start] === args[next]){
      return true
     }
     start++
     next++
     }
     return false
     }

   • set 사용

     function areThereDuplicates() {
     return new Set(arguments).size !== arguments.length;
     }

---

참고

유데미 JavaScript 알고리즘 & 자료구조 마스터클래스