JS 빈도수 세기 패턴

빈도수 세기 패턴

• Object 또는 Set을 사용하여 특정 문자열, 배열의 값 또는 값의 빈도를 수집해서 푸는 패턴
• 이 패턴은 때로, 중첩 루프 또는 O(N^2) 의 배열 / 연산 을 우회할 수 있다.

문제1

• same 이라는 함수를 작성해라
• 이 함수는 배열 2개를 인자로 받는다.
• 1번째 배열의 요소의 제곱이 2번째 배열의 요소로 존재하면서, 그 빈도까지 같다면 True를 반환
• 그것이 아닐 경우에는 false 를 반환

테스트 케이스

same([1, 2, 3], [4, 1, 9]); // true
same([1, 2, 3], [1, 9]); // false
same([1, 2, 1], [4, 4, 1]); // false, 이경우 1의 제곱이 두번 들어가 있지 않기 때문에 false

나의 해답 - 오답

function same(arr1, arr2) {
  arr2.sort((a, b) => a - b);
  const squareArr = arr1.map((x) => Math.pow(x, 2)).sort((a, b) => a - b);
  squareArr.forEach((i, idx) => {
    if (i !== arr2[idx]) {
      console.log(false);
      return;
    }
    console.log(true);
  });
}

해답 1 - O(n^2)

function same_solution(arr1, arr2) {
  // 갯수가 일치하지 않으면 아예 false
  if (arr1.length !== arr2.length) {
    return false;
  }

  // 1번째 배열을 순회하면서 조회
  for (let i = 0; i < arr2.length; i++) {
    // N
    // 1번째 배열의 제곱 값을 가진 arr2의 인덱스를 찾는다.
    let correctIndex = arr2.indexOf(Math.pow(arr1[i], 2)); //N
    // 반환된 인덱스가 -1 일때 false
    if (correctIndex === -1) {
      return false;
    }
    // 정상 인덱스 반환시 인덱스 기준으로 값을 하나씩 제거 한다.
    arr2.splice(correctIndex, 1);
  }
  // 최종 true 반환
  return true;
}

해답 2 - O(n)

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

문제 2

두 개의 문자열이 주어졌을 때, 두 번째 문자열이 첫 번째 문자열의 애너그램인지 확인하는 함수를 작성합니다. 애너그램은 다른 글자의 글자를 재배열하여 형성된 단어, 구 또는 이름입니다. (예시: cinema -> iceman)

테스트 케이스

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

나의 해답 - O(N)

function validAnagram(str1, str2){
    // if str1 === str2 return true
    if(str1 === str2) {
        return true;
    }
    // change lower case string
    str1 = str1.toLowerCase();
    str2 = str2.toLowerCase();
    
    // create frequency counter each string arguments
    let freqCounter1 = {};
    let freqCounter2 = {};
    // Get Count From Each String
    
    // count str1's char
    for (let char1 of str1) {
        freqCounter1[char1] = (freqCounter1[char1] || 0) + 1;
    }
    
    // count str2's char
    for (let char2 of str2) {
        freqCounter2[char2] = (freqCounter2[char2] || 0) + 1;
    }
    
    // compare str1's keys in str2
    for (let key in freqCounter1) {
        // str1's key not in freqCounter 2 return false
        if(!(key in freqCounter2)) {
            return false;
        }
        
        // freqCounter1[key]'s value not Equals freqCounter2[key]'s value return false
        if(freqCounter1[key] !== freqCounter2[key]) {
            return false;
        }
    }
    
  return true;
}

해답 - O(N)

function validAnagram(first, second) {
  if (first.length !== second.length) {
    return false;
  }

  const lookup = {};

  for (let i = 0; i < first.length; i++) {
    let letter = first[i];
    // if letter exists, increment, otherwise set to 1
    lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
  }
  console.log(lookup)

  for (let i = 0; i < second.length; i++) {
    let letter = second[i];
    // can't find letter or letter is zero then it's not an anagram
    if (!lookup[letter]) {
      return false;
    } else {
      lookup[letter] -= 1;
    }
  }

  return true;
}

배운점

• 빈도수를 세는 과제에서는 객체하나를 두고 그안에 추가하여 Counting 하는것이 확실히 이상적인것 같다.

강의

• Udemy : Javascript 자료구조 & 알고리즘 마스터 클래스