[알고리즘] 문제 해결 패턴 (1) 빈도수 세기 패턴

빈도수 세기 패턴

자바스크립트의 객체를 사용해 다양한 값과 빈도를 수집한다. 

 

이 패턴은

• 알고리즘과 여러 데이터와 입력 값이 서로 비슷한 값으로 구성되어 있는지
• 서로 간의 애니그램인지
• 값이 다른 값에 포함되는지 여부를 비교하거나
• 데이터를 입력값이나 두 개 이상의 빈도 혹은 특정하게 발생하는 빈도

와 비교할 때 유용하다.

 

이를 좋은 접근법이자 패턴으로 만들어주는 것은 중첩된 루프와 관련 있거나 n의 제곱 시간을 사용하는 더 쉬운 해결책과 비교했을 때 n²이라 할 수 있다.

관련 문제 예시

두 개의 배열을 입력받는 same이라는 함수를 작성하세요. 이 함수는 첫 번째 배열의 각 값이 두 번째 배열에서 제곱된 값으로 존재하는 경우에 true를 반환해야 합니다. 값의 빈도도 동일해야 합니다.

same([1,2,3], [4,1,9]) // true
same([1,2,3], [1,9]) // false
same([1,2,1], [4,4,1]) // false (must be same frequency)

해결방법(1)

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

  for (let i = 0; i < arr1.length; i++) {
    let correctIndex = arr2.indexOf(arr1 ** 2);
    if (correctIndex === -1) {
      return false;
    }
    array2.splice(correctIndex, 1);
  }
  return true;
}

이러한 접근법은 O(n²), 시간이 사용된다. 

1. 첫번째  for문에서 두 배열의 길이가 다른지에 대한 여부를 즉시 확인 가능
   • arr1, arr2의 값이 다르면 참이 될 수 없다. 
   • 즉, 작동하지 않는다.
2. indexOf를 작성한 이유는 각 값의 제곱을 전달하기 위해서이다. 
3.  
4. correctIndex가 -1인지 확인하고 그렇지 않은 경우 거짓 반환
   • 즉, 대응하는 값이 없다는 의미

indexOf의 기능은 전체 배열을 반복하거나 중첩된 루프인 전체 배열을 잠재적으로 반복한다. 

따라서 n이 배열의 길이를 늘리면 이 값이 이와 값이 이와 같이 증가하여 2차 관계로 중첩된다.

리팩토링

function same(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        
    }
    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}
}

 

첫번째 배열에 루프를 적용하여 두 번째 배열의 하위 후프에서 각 값을 확인하는 대신

각 배열에 한번씩 개별적으로 루프를 적용할 수 있다. (첫번째 for문과 두번째 for문 처럼)

두개의 루프가 두개의 중첩된 개별 루프보다 훨씬 낫다. 이러한 시간 접근법은 O(n)이다. 

 

✅ 빈도수 세기 패턴의 개념은 보통 객체를 사용한다는 것

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

✅  따라서 두 개의 배열을 객체로 세분화하여 각 배열의 요소들을 분류한 다음 각 배열을 비교가능하다.