문제해결 패턴

1. 빈도수 세기 패턴

이 패턴은 object나 set의 값과 빈도를 수집하는데에 사용 된다. 주로 nested loops를 안해도 되게끔 해준다. 주로 O(n)의 답을 가져다준다.

ex) 두 배열을 받는 same이라는 함수를 적어라. 이 함수는 만약 첫번째 배열 내의 모든 값의 두배가 두번째 배열 내에 있는 경우 true를 return 한다.

시간복잡도 O(n)

    function same(arr1, arr2) {
      if (arr1.length !== arr2.length) {
        return false;
      }
      let frequencyCounter1 = {}; // {1: 1, 2: 1, 3: 2}
      let frequencyCounter2 = {}; // {1: 1, 4: 1, 9: 2}
      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; // frequencyCounter1의 key의 제곱값이 frequencyCounter2 의 key 값으로 존재하는지를 확인한다.
        }
        if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
          return false; // 해당 key의 value 값을 확인한다.
        }
      }
      console.log(frequencyCounter1, frequencyCounter2);
      return true;
    }
         console.log(same([1, 2, 3, 3], [9, 9, 1, 4]));

⭐️ 기억할 점! nested loop보다 두개의 loop가 훨씬 좋다!!

👉 기본적으로 빈도수 세기 문제를 풀 때의 핵심은 '객체'를 사용하는 것이다. 두개의 배열을 객체로 쪼개서 만드로 그 안에 있는 것들을 분류한 다음에 두 객체를 비교하였다.

2. 빈도수 세기 : 애너그램 도전 과제

두 문자열이 주어진다. 두 문자열이 서로에 대한 애너그램일 경우 true를 return 한다. 애너그램? 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 놀이이다. ex) cinmena, iceman

 // 나의 풀이
    function validAnagram(str1, str2) {
      if (str1.length !== str2.length) {
        return false;
      }

      let frequencyCounter1 = {};
      let frequencyCounter2 = {};

      for (let val of str1) {
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
      }
      for (let val of str2) {
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
      }

      for (let key in frequencyCounter1) {
        if (!(key in frequencyCounter2)) {
          return false;
        }
        if (frequencyCounter1[key] !== frequencyCounter2[key]) {
          return false;
        }
      }
      return true;
    }

//  선생님 풀이
    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);
      }

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

  console.log(validAnagram("azz", "zza")); //true
  console.log(validAnagram("awesome", "awesom")); // false