Frequency Counter

객체를 사용하자아

두개의 array를 input으로 받아서, array1의 value가 array2의 squared value인지 확인하는 함수를 만들어라. 값이 섞일수는 있지만 arr길이는 동일해야한다.

const arr1 = [1,2,3];
const arr2 = [4,1,9];

same(arr1,arr2) // true

Naive Solution

이 접근법은 nested loop를 사용했기 때문에 시간 복잡도는 O(n^2)이다.
array가 5개의 값을 가지고 있다면 5*5만큼 루프를 돌게 되기 때문이다.

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) return false;
  for (let i = 0; i < arr1.length; i++) {
    let correctInx = arr2.indexOf(arr1[i] ** 2);
    if (correctInx === -1) {
      return false;
    }
    arr2.splice(correctInx, 1); // 이미 계산된 값의 인덱스 제거하기
  }
  return true;
}

Refactorde code

for loop를 3번 사용하였다. 이렇게 loop를 나누게 되면 효율성이 올라간다. array에 5개의 값이 있다면 5N(O(N)), 즉 3*10만큼 loop를 돈다.

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;
}

anagrams

문자 비교뿐만 아니라 횟수도 같이 비교한다.

function same(word1, word2) {
  if (word1.length !== word2.length) return false;
  
   let lookup = {};
  for (let i = 0; i < word1.length; i++) {
    let letter = word1[i];
    lookup[letter] = lookup[letter] ? ++lookup[letter] : 1;
    // console.log(lookup)
  }
  for(let i =0;i<word2.length;i++){
    let letter = word2[i]
    if(!lookup[letter]) return false;
    else{
      lookup[letter] -= 1
    }
  }
  return true
}

1. word1과 word2의 길이가 다르면 무조건 false 리턴하기
2. lookup이라는 객체를 생성하여 key값에는 word1 문자를, value에는 문자 빈도를 할당해준다.
3. word2와 lookup을 비교하여 값이 다르면 false 리턴하기
4. 같다면 lookup의 key값에 있는 value를 -1 해주기
5. 4의 과정을 거친 후, lookup에 있는 key의 value들이 0이 되었는데 value가 0이된 Key값과 arr2의 key값을 비교하면 0(falsy)이기 때문에 if(!lookup[letter]) return false 코드가 실행되면서 false를 리턴하게 된다.

0은 falsy인 것을 잊지말고 기억하자,,✨