알고리즘, 문제해결 패턴, Frequency Counters

Frequency Counters

Frequency Counters는 프로그래밍에서 특정 요소의 발생 빈도를 효율적으로 계산하는 알고리즘 기법입니다. 주로 배열, 문자열 또는 다른 자료 구조 내에서 요소의 빈도를 세어야 할 때 사용됩니다. 이 방법은 일반적으로 시간 복잡도를 줄이고 코드를 보다 효율적으로 만들기 위해 사용됩니다.

기본 개념

Frequency Counter의 기본 개념은 다음과 같습니다:

1. 자료 구조 선택: 주로 해시맵(또는 객체)을 사용하여 각 요소의 발생 빈도를 저장합니다.
2. 반복문 사용: 데이터를 한 번 순회하면서 각 요소의 빈도를 해시맵에 기록합니다.
3. 결과 분석: 필요에 따라 빈도 데이터를 사용하여 문제를 해결합니다.

시간 복잡도

이 자바스크립트 구현은 각 배열 또는 문자열을 한 번만 순회하기 때문에 시간 복잡도는 O(n)입니다. 이는 효율적인 해결책을 제공합니다.

활용 예시

Frequency Counter 알고리즘은 자바스크립트에서 다음과 같은 다양한 문제에 유용하게 사용될 수 있습니다:

• 애너그램(Anagram) 문제 해결
• 배열 내 중복 요소 찾기
• 데이터 집합에서 가장 많이/적게 발생한 요소 찾기
• 주어진 조건에 맞는 부분 배열 찾기

function charCount(str) {
  // 소문자로 변환하기
  // 문자를 하나씩 떼서 배열 안에 넣기
  let arr = [];
  let result = {};

  arr = str.toLowerCase().split('');

  // 배열을 순회하면서 문자의 개수를 세기
  for (let i = 0; i < arr.length; i++) {
    // 0-9, a-z 사이의 문자인지 정규 표현식을 통해 확인하기

    if (!/[0-9a-z]/.test(arr[i])) continue;

    if (result[arr[i]] > 0) {
      result[arr[i]]++;
    } else {
      result[arr[i]] = 1;
    }
  }

  return result;
}

console.log(charCount('Hello')); // { h: 1, e: 1, l: 2, o: 1 }
console.log(charCount('Your Pin is 1234 !'));

/*
{
  '1': 1,
  '2': 1,
  '3': 1,
  '4': 1,
  y: 1,
  o: 1,
  u: 1,
  r: 1,
  p: 1,
  i: 2,
  n: 1,
  s: 1
}
*/

/**
 * 사용한 프로토타입 메서드
 *
 * - String.prototype.toLowerCase: 문자열을 소문자로 변환한다.
 * - String.prototype.split: 문자열을 배열로 변환한다.
 * - RegExp.prototype.test: 문자열이 정규 표현식과 일치하는지 확인한다.
 * - if 문, continue: 반복문을 중단하고 다음 반복으로 넘어간다.
 */

 

배열로 비교

• for 문 내부에서 indexOf로 검색하기 때문에 O(n^2)

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) return false;

    // console.log(arr2);
    arr2.splice(correctIndex, 1);
  }
  return true;
}

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

/**
 * 사용한 프로토타입 메서드
 * - Array.prototype.indexOf: 배열에서 특정 요소를 찾아 인덱스를 반환한다. 없으면 -1을 반환한다.
 * - Array.prototype.splice: 배열에서 특정 요소를 제거한다.
 */

객체로 비교

• for 문 내부를 순회하면서 객체 내부를 index를 기반으로 access 하기 때문에 O(n)

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

  let frequencyCounter1 = {};
  let frequencyCounter2 = {};

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

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

  console.log(frequencyCounter1);
  console.log(frequencyCounter2);

  for (let key in frequencyCounter1) {
    // { key: value } 중 key 체크
    if (!(key ** 2 in frequencyCounter2)) return false;

    // { key: value } 중 value 체크
    if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) return false;
  }

  return true;
}

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

/*
{ '1': 1, '2': 1, '3': 1 }
{ '1': 1, '4': 1, '9': 1 }
true

{ '1': 1, '2': 1, '3': 2 }
{ '1': 1, '4': 1, '9': 2 }
true

false
*/

/**
 * 사용한 프로토타입 메서드
 * - for...of 문: 배열의 요소를 순회한다.
 * - for...in 문: 객체의 키를 순회한다.
 */

Anagram

// time complexity: O(n)

function validAnagram(str1, str2) {
  let strCounter1 = {};
  let strCounter2 = {};

  for (let char of str1) {
    strCounter1[char] = (strCounter1[char] || 0) + 1;
  }

  for (let char of str2) {
    strCounter2[char] = (strCounter2[char] || 0) + 1;
  }

  for (let key in strCounter1) {
    if (!(key in strCounter2)) return false;

    if (strCounter2[key] !== strCounter1[key]) return false;
  }

  return true;
}

console.log(validAnagram('', ''));
console.log(validAnagram('aaz', 'zza'));
console.log(validAnagram('anagram', 'nagaram'));
console.log(validAnagram('rat', 'car'));
console.log(validAnagram('awesome', 'awesom'));
console.log(validAnagram('amanaplanacanalpanama', 'acanalmanplanpamana'));
console.log(validAnagram('qwerty', 'qeywrt'));
console.log(validAnagram('texttwisttime', 'timetwisttext'));

/**
 * validAnagram('', '') // true
 * validAnagram('aaz', 'zza') // false
 * validAnagram('anagram', 'nagaram') // true
 * validAnagram("rat","car") // false) // false
 * validAnagram('awesome', 'awesom') // false
 * validAnagram('amanaplanacanalpanama', 'acanalmanplanpamana') // false
 * validAnagram('qwerty', 'qeywrt') // true
 * validAnagram('texttwisttime', 'timetwisttext') // true
 */