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

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

이 패턴은 말 그대로 객체 또는 Set을 사용하여 특정 문자열, 배열 등의 값 / 값의 빈도를 수집해 풀어내는 방식이다.

 

프로세스

주어진 배열 속 요소의 빈도를 확인할 때, 방식

• Worst : 중첩 루프
  • for문 안에서 indexOf를 사용 -> O(n^2) 

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

• Best : 객체 사용
  • for문을 3번 반복하여 3n. 즉 -> O(n) 

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

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

배열이나 문자열의 내용을 분석하여 비교할 때는 두 개의 배열을 객체로 세분화하여 각 배열의 요소들을 분류한 다음, 각 배열을 비교하는 것이 좋다.

 

ex)

1. 두 개의 배열을 허용하는 same 이라는 함수를 작성한다.
2. 첫 번째 배열의 모든 값이 두번째 배열에 순서와 무관하게 제곱되어 포함될 경우 true 를 반환한다.
3. 단, 빈도는 동일해야 한다.

same([1, 2, 3], [4, 1, 9]) // true
same([1, 2, 3], [1, 9]) // false
same([1, 2, 1], [4, 4, 1]) // false, 빈도가 동일해야 한다.

Naive Solution

const arr1 = [1, 2, 3];
const arr2 = [1, 4, 9];

const same = (arr1, arr2) => {
  const numbers = arr1;
  const squaredNumbers = arr2;
  if (numbers.length !== squaredNumbers.length) { // 두 배열의 길이가 다르면 false 출력
    console.log(false);
    return;
  }

  for (let i = 0; i < numbers.length; i++) {
    let correctIndex = squaredNumbers.indexOf(Math.pow(numbers[i], 2)); // numbers배열의 요소를 제곱한 값이 
    // squaredNumbers 배열에 있으면(index를 반환) correctIndex에 할당한다
    if (correctIndex === -1) { // 값이 없으면 false 출력(indexOf는 값이 없으면 -1을 반환)
      console.log(false);
      return;
    }
    squaredNumbers.splice(correctIndex, 1); // 그 index부터 1개씩 제거
    // i = 0				i = 1				i = 2
    // numbers = [1, 2, 3]		numbers = [1, 2, 3]		numbers = [1, 2, 3]
    // squaredNumbers = [4, 9]		squaredNumbers = [9]		squaredNumbers = []
  }
  console.log(true); // 짝지은 값이 모두 존재하면 true 출력
};

same(arr1, arr2);

가장 일반적인 접근법으로 For loop 내에서 indexOf를 사용해 Nested loop(중첩된 루프)가 사용되고 있어 시간 복잡도는 O(N^2) 이다. Nested loop 보다 두개의 loop 를 사용하는 것이 좋다. 이는 시간 복잡도를 O(N)으로 유지할 수 있다.

 

Frequency counters 패턴을 적용해 리팩토링.

Solution Refactored (Frequency Counter Pattern)

const arr1 = [1, 2, 3];
const arr2 = [1, 4, 9];

const same = (arr1, arr2) => {
  const numbers = arr1;
  const squaredNumbers = arr2;
  
  if (numbers.length !== squaredNumbers.length) {
    // 두 배열의 길이가 다르면 false 출력
    console.log(false);
    return;
  }

  let numbersCounter = {};
  let squaredCounter = {};

  for (let val of numbers) {
    numbersCounter[val] = numbersCounter[val] ? numbersCounter[val] + 1 : (numbersCounter[val] = 1); //numbersCounter[val]키에 해당하는 값이 없으면
    // numbersCounter[val] = 0 + 1;로 추가, 있으면 numbersCounter[val] = numbersCounter[val] + 1; 로 1증가
  }

  for (let val of squaredNumbers) {
    squaredCounter[val] = squaredCounter[val] ? squaredCounter[val] + 1 : (squaredCounter[val] = 1);
  }

  for (let key in numbersCounter) {
    if (!(key ** 2 in squaredCounter)) {
      // 제곱에 해당하는 값이 없으면 false
      console.log(false);
      return;
    }
    if (squaredCounter[key ** 2] !== numbersCounter[key]) {
      // 빈도수가 서로 다르면 false
      console.log(false);
      return;
    }
  }
  // numbersCounter = { 1: 1, 2: 1, 3: 1 };
  // squaredCounter = { 1: 1, 4: 1, 9: 1 };
  console.log(true);
};

same(arr1, arr2);

1. 2개의 객체를 생성하고 1~2번째 for문에서 key(배열의 요소) : value(요소의 개수) 로 채워넣는다.
2. 마지막 for문의 첫번째 if문에서 제곱한 값이 있는지 확인하고
3. 두번째 if문에서 빈도수가 일치하는지 확인한다. (3개의 for loop으로 시간복잡도는 O(N)이다.)

 

결론

• 중첩된 반복문을 피하고, 별개의 반복문으로 나누는 것이 시간복잡도면에서 유리하다.
• 객체에서 value를 찾는 것은 O(N)이지만, key를 찾는 것은 O(1)밖에 걸리지 않으므로 for문 안에서 key를 찾아도 중첩 loop가 아니다.
• 값들의 빈도 계산(Frequency Counter Pattern)시에는 객체나 Set을 만들어서 비교하는 방법이 좋다.

객체를 사용하여 프로파일을 구성하는 것은 배열이나 문자열의 내용을 분석하는 방법으로 보통 배열이나 문자열과 같은 선형 구조를 구성하는 것이다. 이는 해당 분석을 문자열이나 배열에서 생성된 다른객체의 형태와 신속하게 비교할 수 있다.