Frequency Counter - sameFrequency

Udemy - 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스

#1. Frequency Counter - sameFrequency

Write a function called same, which accepts two arrays. The function should return true if every value in the array has it's corresponding value squared in the second array. The frequency of values must be the same.

//시간복잡도: O(n^2)
//indexOf 는 전체 배열을 반복하거나 중첩된 루프인 전체 배열을 잠재적으로 반복하는 것.

function same(arr1, arr2) {
    if(arr1.length !== arr2.length){
        return false;
    }
    for(let i = 0; i < arr1.length; i++){
        let correctIndex = arr2.indexOf(arr1[i]**2)
        if(correctIndex === -1){
            return false;
        }
        // console.log(arr2);
        arr2.splice(correctIndex, 1);
    }
    return true;
}

same([1,2,3,2], [9,1,4,4])

||

REFACTORED

두 개의 루프가 중첩된 개별 루프보다 훨씬 낫다!! (2n 이 n^2보다 나으니까)

V

//시간복잡도: 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
    }
    for (let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key**2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}

---

#Prac1. Frequency Counter - validAnagram

Given two strings, write a function to determine if the second string is an anagram of the first. An anagram is a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.

Note: You may assume the string contains only lowercase alphabets.

Time Complexity - O(n)

validAnagram('', '') // true
validAnagram('aaz', 'zza') // false
validAnagram('anagram', 'nagaram') // true
validAnagram("rat","car") // false
validAnagram('awesome', 'awesom') // false
validAnagram('qwerty', 'qeywrt') // true
validAnagram('texttwisttime', 'timetwisttext') // true

---

🅰️ (제출 답) 

function validAnagram(str1, str2){
  // 문자열 갯수가 다르면 false 반환
  if(str1.length !== str2.length){
      return false;
  }
  // str1을 하나씩 쪼개서 객체에 담아, 같은 글자의 개수는 +한 후 비교
  let frequencyStr1 = {}
  let frequencyStr2 = {}
  for(let val in str1){ //문자열도 배열과 같이 하나씩 for문 돌릴 수 있어
      frequencyStr1[str1[val]] = (frequencyStr1[str1[val]] || 0) + 1;
  }
  for(let val in str2){
      frequencyStr2[str2[val]] = (frequencyStr2[str2[val]] || 0) + 1;
  }
//   console.log(frequencyStr1, frequencyStr2);
  for(let key in frequencyStr1){
      if(!(key in frequencyStr2)){
          return false;
      }
      if(frequencyStr1[key] !== frequencyStr2[key]){
          return false;
      }
  }
  return true;
}

=> 위에서 배운대로 거의 똑같이 풀어봄. 배열이랑 str이라는 차이 등만 고려.

🤼‍♀️  다른 풀이 1

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];
        lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
    }
    for(let i = 0; i < second.length; i++){
        let letter = second[i];
        if(!lookup[letter]){
            return false;
        } else {
            lookup[letter] -= 1;
        }
    }
    return true;
}

=> 접근은 거의 동일하나, object(lookup)를 첫 번째 입력값만 만들어 저장해서 비교하는 것이 다름. 또 두 번째 문자 하나가 첫 번째 문자에 있는 경우(else 조건) -1을 해주지만, 최종적으로 문자 하나가 0이라는 것을 확인할 필요는 없다-는 특징(?)이 있다.

---

#Prac3. Frequency Counter - sameFrequency

Write a function called sameFrequency. Given two positive integers, find out if the two numbers have the same frequency of digits.

Your solution MUST have the following complexities:

Time: O(N)

Sample Input:

1. sameFrequency(182,281) // true
2. sameFrequency(34,14) // false
3. sameFrequency(3589578, 5879385) // true
4. sameFrequency(22,222) // false

---

🅰️ (제출 답) 

function sameFrequency(n1, n2){
  // good luck. Add any arguments you deem necessary.
  //숫자 자릿수가 동일해야 하고
  //첫 번째 숫자를 분리시킨 후, 두 번째 숫자 하나씩 대입시켜서 일치하는지
  //하나씩 제거하는 방법(length = 0)
  const seperateN1 = n1.toString();
  let seperateN2 = n2.toString().split("");
  if(seperateN1.length === seperateN2.length){
     for(let one of seperateN1){
          seperateN2.includes(one) ? seperateN2 = seperateN2.filter(v => v !== one) : seperateN2;
     }
  }
  return seperateN2.length ? false : true;
}

=> 강의 듣기 전에 푼 거라, 조금은 다른(?) 함수들을 가져다 썼다.

- seperateN1에도 split("")를 적용해 배열로 만들어도 되는데, 내장 함수 하나 줄인다고 seperateN2에만 적용.

- 중복되는 숫자가 있을 경우, 삭제하기 위해 seperateN2는 변경 가능하도록 let으로 선언하고 값을 바꾸었다. (불변성 생각하면 좋은 방법은 아닐지도?)

- includes 는 포함하면 true, 아니면 false를 반환하는 함수다.

+ 입력된 두 값의 길이가 다를 경우 false를 반환하는 에러 경계는 비교하기 전에 해주면 좋을 것 같다.

 

🤼‍♀️  다른 풀이 1

    function sameFrequency(num1, num2){
      let strNum1 = num1.toString();
      let strNum2 = num2.toString();
      if(strNum1.length !== strNum2.length) return false;
      
      let countNum1 = {};
      let countNum2 = {};
      
      for(let i = 0; i < strNum1.length; i++){
        countNum1[strNum1[i]] = (countNum1[strNum1[i]] || 0) + 1
      }
      
      for(let j = 0; j < strNum1.length; j++){
        countNum2[strNum2[j]] = (countNum2[strNum2[j]] || 0) + 1
      }
      
      for(let key in countNum1){
        if(countNum1[key] !== countNum2[key]) return false;
      }
     
      return true;
    }

=> 위에서 푼 validAnagram과 거의 동일하다. 숫자 입력이라 문자로 바꾸는 작업이 있고, for문의 방식 차이가 있을 뿐. 다만, 마지막 비교에서 'countNum2의 key에 countNum1의 key가 없으면 false 반환'이라는 옵션은 없는데.. 있고 없고, 어떤 것이 더 효율적인지는 잘 모르겠다.