[알고리즘 | JS] 문제 해결 패턴 소개, 빈도 카운터(Frequency Counter)

🍕Some Patterns (여러 패턴들)

*pattern? 일종의 프로그래밍 메커니즘이나 여러 요소를 넣을 수 있는 청사진 정도

• Frequency Counter (빈도 카운터)
• Multiple Pointers 
• Sliding Window 
• Divide and Counquer (분할 정복)
• Dynamic Programming 
• Greedy Algorithms
• Backtracking
• many more ~!

  ---

🍕Frequency Counter (빈도 카운터)

- 실제로 이런 명칭으로 불리지는 않음 

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

- 해당 패턴을 사용하면 중첩 루프 또는 배열/문자열을 사용하는 O(N^2) 연산을 피할 수 있습니다.

 

아래의 예시를 통해서 알아봅시다. 

Q. 두 개의 배열을 인수로 받는 same이라는 명의 함수를 만드시오.
same함수의 리턴값은 true/ false
if every value in the array has it's corresponding value squared
in the second array. The frequecy of value must be the same.

예측 결과는 아래와 같이 나오면 됩니다.
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

 

▼중첩루프를 사용한 예시(aka. 순진한 접근법)

function same(arr1, arr2) {
  //두 배열의 길이가 같지않으면 false
  if (arr1.length !== arr2.length) {
    return false;
  }
  for (let i = 0; i < arr1.length; i++) {
    // 첫번째 배열을 돌면서 해당 배열의 제곱값이 arr2에 있는 지 확인합니다.
    let correctIndex = arr2.indexOf(arr1[i] ** 2);
    //만일 대응 값이 없다면 (indexOf의 반환값이 -1 이니까)
    if (correctIndex === -1) {
      return false;
    }
    // 루프를 계속 반복하면서 splice를 사용하여 대응되는 제곱값인 correctIndex를 arr2배열에서 제거한다.
    //콘솔에 arr2를 찍어보면서 줄어드는 것을 확인할 수 있다.
    console.log(arr2);
    /* arr2의 내용
    (3) [9, 4, 1]
    (2) [9, 4]
    [9]
    */
    arr2.splice(correctIndex, 1);
  }
  //배열의 요소 중 false를 반환할 것이 없는 [] 빈배열이 되면(즉, arr1의 모든 요소가 arr2의 제곱값으로 상응되어 소거되면) true리턴
  return true;
}
same([1, 2, 3], [9, 4, 1]);

Array.prototype.indexOf( searchElement )

• 매개변수 searchElement 는 배열에서 찾을 요소를 가리킵니다.
• indexOf() 메서드는 배열에서 지정된 요소를 찾을 수 있는 첫 번째 인덱스를 반환합니다.
• 지정된 요소가 존재하지 않으면 -1을 반환합니다.

Array.prototype.splice( start, deleteCount, item )

• 배열의 기존 요소를 삭제 or 교체하거나 새 요소를 추가하여 배열의 내용을 변경
• start 를 제외한 나머지는 optional입니다. item을 지정하지 않을 경우 splice 는 요소를 제거하기만 합니다.
• 리턴값: 제거한 요소를 담은 배열 
• 해당 메소드를 사용하면 원본 배열을 수정하는 것임

-> 해당 예시처럼 접근하면 이 접근법은 O(n^2) 즉, 제곱 시간이 사용되기 때문에 순진한 접근법이라 불립니다. 

• IndexOf의 기능은 전체 배열을 반복하거나 중첩된 루프인 전체 배열을 잠재적으로 반복하는 것입니다.
• 그렇기 때문에 가능하면 중첩된 루프는 시도하지 않는 게 좋습니다. 

---

※아래의 코드는 위의 코드를 리팩토링한 것입니다.

 

▼빈도 카운터 패턴이 적용된 예시

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

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

-첫 번째 배열에 루프를 적용하여 두 번째 배열의 하위 루프에서 각 값을 확인하는 대신에 각 배열에 한 번씩 개별적으로 루프를 적용할 수 있다. 

-해당 예시코드의 Big O는 O(n)이다. 

• 명심할 것: 두 개의 개별 루프가 두 개가 중첩된 하나의 루프보다 훨씬 났다.

---

▶ 빈도 카운터 정리

빈도 카운터의 개념은 보통 객체를 사용한다는 것이다.

객체를 사용하여 프로파일을 구성하는 것이란?

배열이나 문자열의 내용을 분석하는 방법으로 보통 배열이나 문자열과 같은 선형 구조(linear)를 구성하는 것이다.
그러면 해당 분석을 문자열이나 배열에서 생성된 다른 객체의 형태와 신속하게 비교할 수 있다. 
-> 따라서 위의 예시에서 두 개의 배열을 객체로 세분화하여 각 배열의 요소들을 분류한 다음 각 배열을 비교할 수 있다.