(Algorithm) 알고리즘, 문제해결 패턴, 빈도 수 세기 패턴, Frequency Counter

 

 

이번 포스팅은 문제 해결 패턴 중 빈도수 세기 패턴에 대해서 포스팅하고자 한다.

 

해당 패턴은 특정 값의 빈도수를 체크할 때 유용하다.

 

객체나 세트를 이용해, 중복되는 값을 세며, O(N)의 시간복잡도를 갖는다.

 

예시 문제 1

두개의 숫자가 주어졌을 때, 두 숫자의 자릿수가 같은 빈도수를 갖는지 확인하는 함수 sameNumFrequency를 만들어라.

 

[예시 입출력]

sameNumFrequency(12, 21) //true

sameNumFrequency(45512, 25541) //true

sameNumFrequency(1123, 2311) //true

sameNumFrequency(13, 2311) //false

sameNumFrequency(42, 12) //false

sameNumFrequency(2, 22) //false

 

 

1. 먼저 입력받은 두 수를 배열로 만든다.
2. frequency를 셀 수 있는 객체 2개를 생성한다. 
   • frequency1과  frequency2는 각각 첫 번째 숫자(배열)와  두 번째 숫자(배열)의 빈도를 기록하는 데 사용된다.
3. 두 배열의 길이가 다르면 빈도가 무조건 달라지니 false를 반환한다.
4. for문으로 첫번째 배열을 순환하며 frequency에 빈도를 기록한다.
   • 키값이 존재하지 않으면 새로 키값을 만들고 0을 할당하며, 만약 키값이 존재한다면 1을 더한다.
5. frequency1과 frequency2를 비교한다. 만일 빈도수가 다르면 바로 false를 반환한다. 같다면 true를 반환한다.

 

function sameNumFrequency(num1, num2) {
  const arr1 = [...num1.toString()];
  const arr2 = [...num2.toString()];
  const frequency1 = {};
  const frequency2 = {};

  if (arr1.length !== arr2.length) {
    return false;
  }
  
  for (const item of arr1) {
    frequency1[item] = (frequency1[item] || 0) + 1;
  }
  for (const item of arr2) {
    frequency2[item] = (frequency2[item] || 0) + 1;
  }

  for (const key in frequency1) {
    if (!(key in frequency2)) {
      return false;
    }
  }

  return true;
}

 

 

 

 

예시 문제 2

가변적인 인수를 받는 함수가 있다. 해당 함수는 전달받은 인수들 중 중복이 있으면 true를 반환하고 없다면 false를 반환한다.

 

[예시 입출력]

areThereDuplicates(1, 2, 3) // false
areThereDuplicates(1, 2, 2) // true 
areThereDuplicates('a', 'b', 'c', 'a') // true 

areThereDuplicates('a', 'b', 'c', 'd', 'e') // false 

 

 

1. 인수의 갯수를 세기 위해 빈 객체인 frequency를 만든다.
2. 배열로 인수들을 받고, 해당 배열을 순환한다.
3. 인수가 frequency에 있는지 확인한다.
   • 없는 경우 frequency에 해당 인수를 키값으로 저장하고 값으로 1을 저장한다.
   • 있는 경우 true를 반환한다.
4. 배열을 모두 순환해도 중복이 없었다면 false를 반환한다.

function areThereDuplicates(...args) {
  const frequency = {};

  for (const item of args) {
    if (!frequency[item]) {
      frequency[item] = 1;
    } else {
      return true;
    }
  }
  return false;
}