빈도수 패턴(Frequency pattern)

빈도수 패턴(Frequency pattern)은 자바스크립트에서 자주 사용되는 패턴 중 하나이며, 배열(Array)을 다루는데 매우 유용합니다.

빈도수 패턴은 배열의 요소들 중에서 가장 자주 등장하는 요소를 찾는 것입니다. 
이 패턴은 배열에서 요소의 출현 빈도를 계산하여 가장 빈번하게 등장하는 요소를 찾습니다.

빈도수 패턴을 구현하는 방법은 다음과 같습니다.

1. 객체(Object)를 생성합니다.
2. 배열(Array)의 요소들을 반복하면서, 해당 요소가 객체 내에 이미 존재하는지 확인합니다.
3. 만약 해당 요소가 객체 내에 이미 존재한다면, 해당 요소의 값을 1 증가시킵니다.
4. 만약 해당 요소가 객체 내에 존재하지 않는다면, 해당 요소를 객체 내에 추가하고, 값을 1로 설정합니다.
5. 배열(Array)을 모두 반복한 후, 객체(Object) 내에서 가장 큰 값을 가진 요소를 찾습니다.

function findMostFrequent(arr) {
  let frequency = {};
  let max = 0;
  let result = null;
  
  for (let i = 0; i < arr.length; i++) {
    if (!frequency[arr[i]]) {
      frequency[arr[i]] = 1;
    } else {
      frequency[arr[i]]++;
    }
    if (frequency[arr[i]] > max) {
      max = frequency[arr[i]];
      result = arr[i];
    }
  }
  
  return result;
}

console.log(findMostFrequent([1,1,1,2,3,4])) // 1

위의 코드는 배열 내에서 가장 자주 등장하는 요소를 찾는 함수입니다. 이 함수는 배열을 한 번만 반복하므로, 시간 복잡도가 O(n)으로 매우 효율적입니다.

반응형

문제 1. 
첫번째 배열의 제곱값이 두 번째 배열에 해당하는 값을 가지면 True를 반환 그렇지 않다면 false를 반환하는 함수를 작성하세요.

function same(arr1, arr2) {
    // 첫번째 배열과 두번째 배열의 길이가 다르다면 false 반환
    if(arr1.length !== arr2.length) {
        return false;
    }
    // 첫번째 배열의 길이만큼 반복
    for(let i = 0; i < arr1.length; i++){
        // 변수를 하나 생성하여 두번째 배열에 첫번재 배열의n번째 값의 제곱값이 있다면 해당 인덱스를 저장
        // indexOf는 해당 값이 존재하지 않으면 -1 반환
        let correctIndex = arr2.indexOf(arr1[i] ** 2)
        
        // 두번째 배열에 존재하지 않는다면 false 반환
        if(correctIndex === -1){
            return false;
        }
        // 두번째 배열에 존재한다면 해당 인덱스를 잘라냄
        arr2.splice(correctIndex, 1)
    }
        return true;
}

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

위의 코드로 함수를 작성하여 문제를 해결 하였지만 한가지 문제점이 있습니다.
첫번째 배열의 길이만큼 반복하는 for문안에 두번째 배열에 첫번째 배열의 제곱값이 있는지를 찾는 indexOf가 사용되었기 때문입니다.
indexOf는 배열의 길이만큼 전부 돌면서 해당 값을 검색하게 됩니다.
반복문안에 반복문이 또 있기 때문에 해당 함수의 성능은 O(n^2)이 됩니다.

해당 문제는 빈도수 패턴을 적용하여 성능을 더 향상 시킬수 있습니다.

function same(arr1, arr2) {
    // 첫번째 배열과 두번째 배열의 길이가 다르면 false 반환
    if(arr1.length !== arr2.length){
        return false;
    }
    // 객체 생성
    let frequencyCounter1 = {}
    let frequencyCounter2 = {}

    for(let val of arr1) {
        // 오브젝트의 키값을 추가하고 그값이 이미 존재한다면 +1 없으면 1로 셋팅
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
    }
    for(let val of arr2) {
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1
    }
    // 첫번째 객체만큼 반복
    for(let key in frequencyCounter1) {
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}

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

빈도수 패턴으로 예제의 코드를 리팩토링 해보았습니다. 해당 코드에서는 3개의 for문이 사용되었으나 중첩된 for문은 없습니다. 빅오 표기법으로 나타내면 O(3n)이 되지만 추세를 보았을때 결국 O(n)이 됩니다.
즉, 첫번째 함수와 두번째 함수 모두 똑같은 기능을 동작하지만 두번째 함수가 성능이 더 좋습니다.

문제를 해결함에 있어 자주 쓰이는 패턴들이 있습니다. 앞으로 몇가지 패턴들에 대해 알아보도록 하겠습니다.