2.1Frequency Counters

Frequency Counters(빈도 수 세기 패턴)

Frequency Counter 패턴은 객체나 Set을 활용해 key에 값을 저장하고, 해당 값의 빈도(등장 횟수)를 기록하고 비교하는 방식이다. 이 패턴은 배열이나 문자열에서의 중첩 반복문(O(n²))을 단일 반복문(O(n))으로 바꾸는 데 유용하다.

예시 1: Comparing Two Arrays

두 개의 배열을 입력받아, 첫 번째 배열의 각 값들이 두 번째 배열에 제곱된 형태로 존재하고, 그 빈도(frequency)도 동일한 경우에만 true를 반환하는 same이라는 함수를 작성하라.

예를 들면,

javascript
same([1, 2, 3], [4, 1, 9]) // true
same([1, 2, 3], [1, 9])    // false (길이가 다름)
same([1, 2, 1], [4, 4, 1]) // false (빈도 불일치)

비효율적인 풀이

가장 먼저 떠오를 수 있는 접근 방식은 아래와 같다.

javascript
function same(arr1, arr2){
  if (arr1.length !== arr2.length) {
    return false;
  }
  for (let i = 0; i < arr1.length; i++) {
    let correctIndex = arr2.indexOf(arr1[i] ** 2);
    if (correctIndex === -1) { 
      // arr2에는 arr1에 있는 요소의 제곱 값이 존재하지 않는 경우
      return false;
    }
    // 중복 방지를 위해 한번 확인된 요소는 arr2에서 제거
    arr2.splice(correctIndex, 1); 
  }
  return true;
}

우선 두 배열의 길이가 다르면 빈도수가 반드시 다르므로 false를 반환한다.

첫 번째 배열의 각 요소들을 loop하며, 각 요소마다 또 두 번째 배열의 각 요소들을 loop하며 비교한다. 두 번째 배열에 첫 번째 배열의 요소를 제곱한 값이 있다면, 해당 값은 splice로 없애고, 첫 번째 배열의 다음 요소를 loop한다. 만약 첫 번째 배열의 요소를 제곱한 값을 두 번째 배열에서 찾을 수 없다면 false를 반환하고, 끝까지 루프가 돌면 true를 반환한다.

이 코드는 논리적으로는 맞지만, 2중 for문을 쓰며 시간 복잡도가 O(n²)에 달한다. 즉, 배열이 커짐에 따라 성능이 급격히 나빠지는 방법이다.

효율적인 방법: Frequency Counter

각 배열의 값들을 객체에 저장하여 빈도를 비교하면, 시간 복잡도를 O(n)으로 줄일 수 있다.

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

  const frequencyCounter1 = {};
  const 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) {
    const squared = key ** 2;

    if (!(squared in frequencyCounter2)) {
      return false;
    }

    if (frequencyCounter2[squared] !== frequencyCounter1[key]) {
      return false;
    }
  }

  return true;
}

두 배열을 한 번씩만 for문으로 루프하며 값을 기록하고, 비교는 마지막에 한다.

예시 2: Anagram 판별

두 개의 문자열이 주어졌을 때, 두 번째 문자열이 첫 번째 문자열의 **애너그램(anagram)**인지 판별하라.
(대소문자 구분할 필요 없음, 공백 및 숫자 없음)

애너그램이란 아래와 같이 문자열을 구성하는 문자들과 빈도수가 같은 두 문자열이다.

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

Frequency Counter를 써서 아래와 같은 알고리즘을 작성할 수 있다. 첫번째 문자열으로부터 각 문자의 빈도를 객체에 저장하고, 두 번째 문자열을 loop하며 빈도를 확인한다.

javascript
function validAnagram(first, second){
  if(first.length !== second.length) return false;

  const lookup = {};

  for (let i = 0; i < first.length; i++){
    let letter = first[i];
    // letter가 존재하면 1 더하고, 아니면 1로 설정
    lookup[letter] = (lookup[letter] || 0) + 1;
  }
  for(let i = 0; i < second.length; i++){
    let letter = second[i];
    // letter가 없거나 letter가 0이면 anagram 아님
    if(!lookup[letter]) return false;
      lookup[letter] -= 1;
  }

  return true;
}

• 첫 번째 루프에서 각 문자의 등장 횟수를 기록하고,
• 두 번째 루프에서 차감하며 확인한다.

---

🤠 개인 탐구

Anagram 문제 내 풀이 복기

나는 아래와 같이 풀었다. 첫 번째 문제의 풀이를 많이 참고한 방식으로, 각 문자열에 대해 frequencyCounter를 각각 만들고 다시 for문으로 비교했다.

javascript
function validAnagram(str1, str2){
    if(str1.length !== str2.length){
        return false
    }
    
    const frequencyCounter1 = {};
    const frequencyCounter2 = {};
    const arr1 = [];
    const arr2 = [];
    toArr(str1, arr1);
    toArr(str2, arr2);
    
    // str1 count
    for (const val of arr1){
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) +1;
    }
    
    // str2 count
    for (const val of arr2){
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) +1;
    }
    // 비교
    for (const key in frequencyCounter1){
        if(frequencyCounter2[key] !== frequencyCounter1[key])
            return false
    }   
    return true
}

// str를 array로
function toArr(str, arr){
    for(let i=0; i < str.length; i++){
        arr[i] = str.slice(i, i+1)
    }
}

개선할 수 있었던 부분들을 생각해보면,

• 일단 toArr라는 함수를 만들 필요가 없었다. split("")으로 적었으면 되었는데 깜빡했다.
• 객체를 굳이 두 개 만들고 비교할 필요가 없이, 하나의 객체(lookup)를 만들어도 충분했다.
  • 두 개를 만들면 메모리 효율이 떨어진다.

TypeScript로 답안 작성해보기

1번 문제: same함수 (두 배열의 제곱 관계 확인)

• Record 타입을 활용하면 된다.
• key는 for...in문에서 문자열로 반환되므로 Number(key)로 변환해야 한다.

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

  const frequencyCounter1: Record<number, number> = {};
  const frequencyCounter2: Record<number, number> = {};

  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) {
    const squared = Number(key) ** 2;

    if (!(squared in frequencyCounter2)) {
      return false;
    }

    if (frequencyCounter2[squared] !== frequencyCounter1[Number(key)]) {
      return false;
    }
  }

  return true;
}

1. validAnagram 함수

javascript
function validAnagram(first: string, second: string): boolean {
  if (first.length !== second.length) return false;

  const lookup: Record<string, number> = {};

  for (let i = 0; i < first.length; i++) {
    const letter = first[i];
    lookup[letter] = (lookup[letter] || 0) + 1;
  }

  for (let i = 0; i < second.length; i++) {
    const letter = second[i];
    if (!lookup[letter]) return false;
    lookup[letter] -= 1;
  }

  return true;
}