(알고리즘) (알고리즘 패턴) 주파수 계수기

쉬운 목차

주파수 카운터 알고리즘의 패턴

이 패턴은 말 그대로 객체나 세트를 사용하여 주어진 문자열, 배열 등의 값/값의 빈도를 수집하고 공유하는 방식입니다.

소송 절차

주어진 배열에서 요소의 빈도를 확인할 때 메서드는

최악: 중첩 루프
- for 문에서 indexOf 사용 -> 오(n^2)

for A 순회 
  B.indexOf(n) 찾아서 삭제 
  없으면 return false 
  순회 마쳤으면 return true

최고: 객체 사용
- for 문을 세 번 반복하여 3n. 즉 -> 에)

A 순회해서 {요소: 개수, ...} 객체 만듬 
B 순회해서 {요소: 개수, ...} 객체 만듬 
A객체의 key 순회해서 B객체 값과 비교 
  같지 않으면 return false 
  순회 마쳤으면 return true

주파수 카운터는 일반적으로 개체를 사용합니다.

배열 또는 문자열의 내용 구문 분석 및 비교 두 배열을 객체로 나누어 각 배열의 요소를 분류한 후, 각 배열을 비교하는 것이 좋습니다.

전)

두 개의 배열을 받는 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, 빈도가 동일해야 한다.

순진한 솔루션

const arr1 = (1, 2, 3);
const arr2 = (1, 4, 9);

const same = (arr1, arr2) => {
  const numbers = arr1;
  const squaredNumbers = arr2;
  if (numbers.length !== squaredNumbers.length) { // 두 배열의 길이가 다르면 false 출력
    console.log(false);
    return;
  }

  for (let i = 0; i < numbers.length; i++) {
    let correctIndex = squaredNumbers.indexOf(Math.pow(numbers(i), 2)); // numbers배열의 요소를 제곱한 값이 
    // squaredNumbers 배열에 있으면(index를 반환) correctIndex에 할당한다
    if (correctIndex === -1) { // 값이 없으면 false 출력(indexOf는 값이 없으면 -1을 반환)
      console.log(false);
      return;
    }
    squaredNumbers.splice(correctIndex, 1); // 그 index부터 1개씩 제거
    // i = 0				i = 1				i = 2
    // numbers = (1, 2, 3)		numbers = (1, 2, 3)		numbers = (1, 2, 3)
    // squaredNumbers = (4, 9)		squaredNumbers = (9)		squaredNumbers = ()
  }
  console.log(true); // 짝지은 값이 모두 존재하면 true 출력
};

same(arr1, arr2);

가장 일반적인 접근 방식은 for 루프 내에서 indexOf를 사용하여 중첩 루프를 만드는 것입니다. 시간 복잡도는 O(N^2) 오전. 중첩된 루프 대신 두 개의 루프를 사용하는 것이 좋습니다. 이것은 시간 복잡도 O(N)을 유지할 수 있습니다.

주파수 카운터 패턴을 적용하도록 수정되었습니다.

재설계된 솔루션(주파수 카운터 패턴)

const arr1 = (1, 2, 3);
const arr2 = (1, 4, 9);

const same = (arr1, arr2) => {
  const numbers = arr1;
  const squaredNumbers = arr2;
  
  if (numbers.length !== squaredNumbers.length) {
    // 두 배열의 길이가 다르면 false 출력
    console.log(false);
    return;
  }

  let numbersCounter = {};
  let squaredCounter = {};

  for (let val of numbers) {
    numbersCounter(val) = numbersCounter(val) ? numbersCounter(val) + 1 : (numbersCounter(val) = 1); //numbersCounter(val)키에 해당하는 값이 없으면
    // numbersCounter(val) = 0 + 1;로 추가, 있으면 numbersCounter(val) = numbersCounter(val) + 1; 로 1증가
  }

  for (let val of squaredNumbers) {
    squaredCounter(val) = squaredCounter(val) ? squaredCounter(val) + 1 : (squaredCounter(val) = 1);
  }

  for (let key in numbersCounter) {
    if (!(key ** 2 in squaredCounter)) {
      // 제곱에 해당하는 값이 없으면 false
      console.log(false);
      return;
    }
    if (squaredCounter(key ** 2) !== numbersCounter(key)) {
      // 빈도수가 서로 다르면 false
      console.log(false);
      return;
    }
  }
  // numbersCounter = { 1: 1, 2: 1, 3: 1 };
  // squaredCounter = { 1: 1, 4: 1, 9: 1 };
  console.log(true);
};

same(arr1, arr2);

두 개의 객체를 생성하고 1st 및 2nd for 문에서 키(배열 요소) : 값(요소 수) 그것을 채우다
마지막 for 문의 첫 번째 if 문에 제곱 값이 포함되어 있는지 확인
두 번째 if 문에서 빈도가 일치하는지 확인합니다. (3 for 루프의 시간 복잡도는 에)오전.)

졸업 증서

시간적으로 중첩된 루프를 피하고 별도의 루프로 나누는 것이 유리합니다.
객체에서 값 찾기 에)하지만 열쇠는 찾아야 한다 오(1)하나만 사용하기 때문에 for 문에서 키를 찾더라도 중첩 루프가 아닙니다.
값의 빈도(Frequency Counter Pattern)를 계산할 때 객체를 생성하거나 설정하여 비교하는 것이 좋습니다.

개체를 사용한 프로파일링은 일반적으로 배열이나 문자열과 같은 선형 구조를 만드는 배열 또는 문자열의 내용을 구문 분석하는 방법입니다. 이를 통해 해당 분석을 문자열이나 배열에서 생성된 다른 개체의 모양과 빠르게 비교할 수 있습니다.