Frequency Counter

출처: https://unsplash.com/ko/%EC%82%AC%EC%A7%84/o7A9d-V-8MU

해당 글은 Udemy "JavaScript 알고리즘 & 자료구조 마스터 클래스" 수업을 기반으로 작성한 내용입니다.

 

Frequency Conter 패턴은 두 데이터를 서로 대응하여 비교하는 경우에 주로 사용됩니다. 밑에서 문제로 살펴 보겠지만, 예를들어 아나그램(단어를 재배열하여 다른 의미의 단어로 변경하기), 한 배열의 숫자 요소를 제곱한 값이 다른 배열의 요소와 1:1 매칭하여 비교하는 경우 등이 있습니다. 

 

Frequency Conter 패턴의 주로 객체를 통해 구현됩니다. 입력 받은 데이터는 주로 배열과 문자열과 같은 선형 데이터 구조가 사용되는데 해당 데이터를 객체로 세분화 하여 key, value의 형태로 만들게 됩니다. 

 

보통 O(log n), O(n²)의 시간복잡도를 피하고 O(n)의 시간복잡도로 문제를 해결할 수 있습니다. 즉, 중첩 반복문을 사용하지 않고 구현할 수 있습니다.

 

same, validAnagram 두 문제를 통해 Frequency Conter 패턴을 구현해 보도록 하겠습니다. 

 

 

same

해당 문제는 인자로 숫자를 담은 arr1, arr2 두 배열을 받아 arr1 배열 요소를 제곱한 값이 arr2 배열의 요소와 1:1 매칭이 되는지 찾는 문제입니다. 모든 요소가 짝을 이루어야 하기 때문에 배열의 개수가 동일해야 합니다.

 

먼저 Frequeny Counter 형식을 사용하지 않고 brute force 방법을 사용하여 구현해보겠습니다.

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) return false;

  for (let i = 0; i < arr1.length; i++) {
    for (let j = 0; j < arr2.length; j++) {
      if (arr1[i]**2 === arr2[j]) {
        arr2.splice(j, 1);
      }
    }
    if (!arr2.length) return true;
  }
  return false;
}

1. 두 배열의 길이(요소의 개수)가 다르면 1:1 매칭이 되지 않기 때문에 false를 반환합니다.
2. 이중 반복문을 순회하면서 arr1의 제곱한 요소와 arr2 요소가 같은지 비교합니다.
3. 만약 두 요소가 같다면 문제의 조건에 일치하는 값이므로 arr2에서 해당 요소를 제거합니다.
4. 반복문이 종료되는 시점에 arr2에 아무 요소가 남아있지 않았다면 모두 일치하였다는 뜻이 되기 때문에 true를 반환 합니다.
5. 반대로 반복문이 종료되어도 arr2 배열에 요소가 남아있다면 일치하지 않는 요소가 있다는 뜻이므로 false를 반환합니다. 

 

function same(arr1, arr2) { 
  if (arr1.length !== arr2.length) return false; 

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

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

  for (const key in frequencyCounter1) {
    if (!(key ** 2 in frequencyCounter2)) {
      return false;
    }
    if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
      return false;
    }
  }
  return true;
}

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

1. 위의 방법에서와 마찬가지로 두 배열 각 요소의 빈도수는 같아야 하기 때문에 배열의 길이가 다른 경우는 false 리턴합니다.
2. 두 배열의 빈도수를 체크할 수 있는 객체 형태의 카운터를 각각 생성합니다.(frequencyCounter1, frequencyCounter2) 
3. 두 배열을 순회하면서  배열 요소를 키로 빈도수를 값으로 각 카운터를 완성합니다.
4. 마지막으로 for...in 문을 사용해서 최종 생성된 두 개의 카운터를 통해 

 

 

validAnagram

validAnagram은 입력값으로 들어온 두 문자열이 애너그램의 규칙을 따르는지 확인하는 알고리즘 문제입니다. 애너그램이란 어떤 단어의 문자를 재배열하여 다른 뜻을 가지는 다른 단어로 바꾸는 것으로 listen을 재조합해 slient라는 단어로 바꿀 수 있습니다.

 

일반적인 Anagram(애너그램)은 silent와 같이 재배열을 통해 만들어진 단어가 의미가 있어야 하지만 해당 알고리즘 문제에서는 입력값으로 들어온 두 문자열이 단어로써 의미가 있는것은 상관없고 다른 형태로 단순 재배열 되었는지만 확인하면 됩니다. 결국 각 문자열의 개별 요소의 빈도수가 같은지 확인하여 true, false를 반환하면 되는 것입니다.  

 

먼저 순간적으로 떠올릴 수 있는 단순한 방법으로 구현해보겠습니다.

function validAnagram(s, t){
  if (s.length !== t.length) return false;
    
  const sortedS = [...s].sort();
  const sortedT = [...t].sort();

  for (let i = 0; i < sortedS.length; i++) {
    if (sortedS[i] !== sortedT[i]) return false;
  }

  return true;
}

각 단계를 세부적으로 살펴보면 다음과 같습니다.

1. 입력값 s, t 두 문자열의 길이가 다른 경우 false 반환하는 얼리리턴 처리를 합니다.(위에서 살펴본 바와 같이 각 문자가 1:1 매칭이 꼭 되어야 하기 때문!)
2. sortedS, sortedT 에 각각 s, t 문자열을 스프레드 문법과 sort 메서드를 사용하여 각 문자를 요소를 오름차순으로 정렬한 배열을 만습니다.
3. 반복문을 통해 만들어진 두 배열(sortedS, sortedT)을 순회하며 비교를 합니다.
4. 오름차순으로 정렬했기 때문에 각 위치(인덱스)에 있는 요소가 동일하지 않으면 false를 반환합니다.
5. 위 반복문 비교 과정을 통과한 경우 true를 반환합니다. 

해당 구현과정은 JavaScript Array 내장 메서드인 sort를 사용했기 때문에 최악의 경우(worst case)에는 O(n²)의 시간복잡도를 갖습니다. JavaScript의 sort 메서드는 퀵 정렬(quick sort), 합병 정렬(merge sort) 등의 알고리즘을 사용하여 구현된 메서드입니다.

 

 

다음은 Frequeny Counter 접근 방식을 통해 문제를 풀어보겠습니다.

function validAnagram(s, t) {
  if (s.length !== t.length) return false;
  
  const lookup = {};
  
  for (let i = 0; i < s.length; i++) {
    let letter = s[i];
    lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
  }
  
  for (let i = 0; i < t.length; i++) {
    let letter = t[i];
    
    if (!lookup[letter]) {
      return false;
    } else {
      lookup[letter] -= 1;
    }
    
  return true;  
}

1. 입력값 s, t 두 문자열의 길이가 다른 경우 false 반환하는 얼리리턴 처리를 합니다.
2. lookup 이라는 빈 객체를 선언합니다.
3. 문자열 s를 순회하면서 각 문자를 키(key)로 빈도수를 값(value)으로 하여 lookup 객체에  담습니다. 해당 문자가 존재하지 않는다면 값(value)에 1을 부여하고 존재한다면 기존 값(value)에 1을 더해나갑니다.
4. 문자열 s를 활용하여 만들어진 lookup 객체를 문자열 t의 문자를 키(key)로 하여 해당 문자에 대한 값의 여부를 체크합니다. 값이 1 이상이라면 해당 문자의 값(value)에서 1을 빼주고 존재하지 않는다면 false를 반환합니다.
5. 모든 순회를 무사히 마쳤으면 두 문자열이 완전히 동일하다는 뜻이므로 true를 반환합니다.

 

이상으로 Frequency Counter 패턴을 알아보았습니다.