[JS 알고리즘] 빈도수 세기 패턴 ( Frequency Counter )

아래 강의를 듣고 내용을 정리한 포스트 입니다

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

JavaScript (JS) Algorithms and Data Structures Masterclass

 

패턴 이름 없이 개념으로부터 비롯된 이름으로 'Frequency Counter Pattern'이라고 부르기도 합니다. 이 패턴은 JavaScript 객체를 이용해 다양한 값을 수집하고 비교하는 패턴입니다.

두 데이터셋이 서로 유사한지, 아나그램인지, 값이 다른 값에 포함되는지, 두 개 이상의 빈도 혹은 특정하게 발생하는 빈도와 비교할 때 유용합니다.

언제 사용하는가 ?

- 배열, 문자열
- 일반적인 방법으로 중첩된 루프가 필요해 지거나 n^2 시간을 사용하는 알고리즘일때
- 서로 비슷하거나 같은가?
- 서로 아나그램인가?
- 하나의 값이 다른 값에 포함되는가?
- 입력값이나 두개 이상의 빈도 혹은 특정하게 발생하는 빈도와 비교할때

필요 조건 : 같은 크기의 배열, 문자열을 비교할때 중첩 루프가 필요한 경우
핵심 : 빈도수 비교를 하기위해 객체를 사용한다. 배열이나 문자열을 한개씩 탐색하는게 아닌, 객체의 키로 바로 접근한다.

예제 1

// 두개의 숫자 배열이 서로 제곱 관계이면 true, 아니면 false 를 반환하는 함수 same() 을 작성하라

same([1,2,3], [4,1,9]) // true
same([1,2,3], [1,9]) // false
same([1,2,1], [4,4,1]) // false

// 첫번째 배열과 두번째 배열이 서로 제곱관계인지 판별

// 첫번째 배열에 루프를 적용해 두번째 배열의 하위 루프에서 각 값을 확인하는 대신
// 각 배열에 한번씩 개별적으로 루프를 적용한다
// O(n^2) => O(n)

const same = (arr1: number[], arr2: number[]) => {
  if (arr1.length !== arr2.length) {
    return false;
  }

  let freqCnt1 = {};
  let freqCnt2 = {};

  for (let val of arr1) {
    freqCnt1[val] = (freqCnt1[val] || 0) + 1;
  }

  for (let val of arr2) {
    freqCnt2[val] = (freqCnt2[val] || 0) + 1;
  }

  // freqCnt1 = { '1': 1, '2': 2, '3': 1 }
  // freqCnt2 = { '1': 1, '4': 2, '9': 1 }

  for (let key in freqCnt1) {
    // freqCnt1['2'] 의 제곱 '4' 가 freqCnt2 에 존재 하는가?
    if (!(Number(key) ** 2 in freqCnt2)) {
      return false;
    }

    // freqCnt2[2] 의 제곱 4 의 value 가 freqCnt1[2] 의 value 와 같은가?
    if (freqCnt2[Number(key) ** 2] !== freqCnt1[key]) {
      return false;
    }
  }

  return true;
};

console.log(same([1, 2, 3, 2], [9, 1, 4, 4])); // true

위의 코드에서는 두 배열에 각각 루프를 적용하여 각 값들의 빈도수를 계산하고, 이를 바탕으로 두 배열이 서로 제곱 관계인지를 판별합니다. 이를 위해 먼저 두 배열의 길이가 다르면 false를 반환하고, 각 배열의 값들의 빈도수를 계산한 뒤, 이를 비교하여 두 배열의 값들이 서로 제곱 관계인지를 판별합니다.

이 코드의 시간 복잡도는 O(n)으로, 첫 번째 배열에 루프를 적용해 두 번째 배열의 하위 루프에서 각 값을 확인하는 대신, 각 배열에 한 번씩 개별적으로 루프를 적용하여 값을 확인하므로 두 배열의 길이에 비례하는 선형 시간이 소요됩니다.

예제 2

// 두 문자열이 서로 아나그램이라면 true, 아니면 false 를 반환 하는 함수 validAnagram 을 작성하라.

validAnagram('', '') // true
validAnagram('anagram', 'nagaram') // true
validAnagram('rat', 'car') // false
validAnagram('aaz', 'zza') // false

const validAnagram = (str1: string, str2: string) => {
  if (str1.length !== str2.length) return;

  let freq1 = {};
  let freq2 = {};

  for (let val1 of str1) {
    if (freq1[val1]) {
      freq1[val1] += 1;
    } else {
      freq1[val1] = 1;
    }
  }

  for (let val2 of str2) {
    if (freq2[val2]) {
      freq2[val2] += 1;
    } else {
      freq2[val2] = 1;
    }
  }
  
  for (let key in freq1) {
  	// key 가 존재하지 않는다면
    if (!(key in freq2)) {
      return false;
    }

	// 서로 값이 다르다면
    if (freq1[key] !== freq2[key]) {
      return false;
    }
  }

  return true;
};

console.log(validAnagram('anagram', 'nagaram')); // true

문자열의 길이가 다른 경우, 서로 다른 문자열이므로 false를 반환하게 되며, 아니라면 두 문자열을 순회하면서 각 문자가 몇 번 등장하는지 확인하고, 그 빈도수를 객체에 저장합니다. 마지막으로, 두 객체가 같은지 비교하여 결과를 반환합니다.

이와 같이, 각 요소가 몇 번 등장하는지 세어주는 객체를 사용하면, 배열, 문자열 등 다양한 자료구조에 대해 효율적으로 문제를 해결할 수 있습니다. 배열, 문자열 등의 순회 대신에 객체의 속성을 이용하여 문제를 해결하는 것이 더욱 효율적일 수 있습니다.