[자바스크립트 빈도수 세기패턴]

유데미 자바스크립트알고리즘& 자료구조 마스터 클래스 Colt Steele강의를 듣고 공부한 내용을 정리한 것입니다.
 
 
 
선형시간 n^2
주석을 보면 설명이 있습니다.
 

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) {
    return false;
  }
  // 선형시간 n제곱
  // 하나의 for루프밖에 없어서 전체배열을 반복함
  for (let i = 0; i < arr1.length; i++) {
    let correctIndex = arr2.indexOf(arr1[i] ** 2);
    // 제곱 해서 해당 값이 없으면 false
    if (correctIndex === -1) {
      return false;
    }
    console.log(arr2);

    // 배열의 인덱스 첫번째 값을 삭제
    // ex) [9,1,4,4] -> 1의제곱삭제 [9,4,4] -> 2의제곱삭제 [9,4] -> 3의제곱삭제 [4]
    // 마지막배열인 2의제곱삭제 []
    arr2.splice(correctIndex, 1);
  }
  return true;
}

same([1, 2, 3, 2], [9, 1, 4, 4]);

 
결과
[9,1,4,4]
[9,4,4]
[9,4]
[4]
true  
 
 
 
 
선형시간 2n
차이점은 for루프가 분기되 있는것을 볼 수 있습니다.  n^2은 점점 숫자가 불어서 선형시간이 최악입니다.
결론은 n^2  <  2n이 낫습니다.
 

// 선형시간 2n
function same(arr1, arr2) {
  // 배열 길이 확인
  if (arr1.length !== arr2.length) {
    return false;
  }
  let frequencyCounter1 = {};
  let frequencyCounter2 = {};
  for (let val of arr1) {
    // var에 1을 더하거나 이미포함되어 있다면 1로 초기화
    // 암묵적 숫자 타입 변환 {[] || 0} + 1 = 1
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
  }

  // var에 1을 더하거나 이미포함되어 있다면 1로 초기화
  // 암묵적 숫자 타입 변환 {[] || 0} + 1 = 1
  for (let val of arr2) {
    frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
  }

  // 카운터1의객체값 제곱한 것이 카운터2에 없으면  false
  // ex) 2의 제곱은 4가 있으니 True
  for (let key in frequencyCounter1) {
    if (!(key ** 2 in frequencyCounter2)) {
      return false;
    }
    // ex) 카운터1,2 키의 개수가 같아야함
    if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
      return false;
    }
  }
  console.log(frequencyCounter1);
  console.log(frequencyCounter2);

  return true;
}

same([1, 2, 3, 2], [9, 1, 4, 4]);

 
결과 
{ '1': 1, '2': 2, '3': 1 }
{ '1': 1, '4': 2, '9': 1 }