알고리즘&자료구조 스터디 3주차 [Frequency Counter]

April 20, 2023 🐰

☺︎ 어려운 문제에 어떻게 접근할까?

• 문제를 해결하기 위한 계획을 수립하기 -> section 4 :문제 해결 접근법
• 일반적인 문제 해결 패턴을 습득하기 (Problem solving Patterns) -> 오늘 정리할 것!
• 그렇다.. 오늘도 강의는 코딩하는법을 돌리고 돌려서 어렵게 말한다.

☺︎ 일반적인 문제 해결 패턴을 습득하기 (Problem solving Patterns)

💪🏻 이 친구들은 알고리즘을 패턴화해 문제 해결에 도움을 줄 수 있는 착한 친구들이다!

앞으로 다 공부할 예정!

🧠 frequency Counter
🧠 Multiple Pointers
🧠 Sliding Window
🧠 Divide and Conquer
🧠 Dynamic Programming
🧠 Greedy Algorithms
🧠 Backtracking
🧠 Many More!!!

🧠 Frequency Counters

• 빈도수 세기는 자바스크립트의 객체를 사용해서 다양한 값과 빈도를 수집하는 것이다.(정식적인 이름은 없음😥)

Step by Step!

• 여러 데이터와 입력값이 서로 비슷한 값으로 구성
• 값이 다른 값에 포함되는지 여부를 비교할 때
• 데이터를 입력값이나 두개 이상의 빈도, 혹은 특정하게 발생하는 빈도와 비교할 때 유용

👩🏻‍🌾 Coding Exercise 0: basic frequency counters Pattern

2개의 배열을 허용하는 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 (must be same frequency)

👩🏻‍🌾 기본 방법 O(N^2)

function same(arr1, arr2) {
  //길이가 다르면 일단 false
  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;
    }
    arr2.splice(correctIndex, 1);
  }
  return true;
}

1. 각 문자의 길이 확인 -> 길이가 다르면 => false
2. for문 안에서 index값을 값의 제곱값에 저장
   -> 제곱의 값이 없을 경우(-1일 때) => false
   -> 존재할 경우에 splice를 통해 제거
3. 최종적으로 => true

Array.prototype.indexOf() - JavaScript | MDN
indexOf() 메서드는 배열에서 지정된 요소를 찾을 수 있는 첫 번째 인덱스를 반환하고 존재하지 않으면 -1을 반환합니다.

Array.prototype.splice() - JavaScript | MDN
splice() 메서드는 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경합니다.

👩🏻‍🌾 Refactor version O(N)

function same(arr1, arr2) {
  //길이가 다르면 일단 false
  if (arr1.length !== arr2.length) {
    return false;
  }
  //Frequency measurement object
  let frequencyCounter1 = {};
  let frequencyCounter2 = {};

  // for 문을 통해 접근 ..
  // 해당값이 존재하면 1을 추가, 없으면 0 으로 초기화
  for (let val of arr1) {
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
  }
  // 해당값이 존재하면 1을 추가, 없으면 0 으로 초기화
  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;
    }
  }
  console.log(frequencyCounter1);
  console.log(frequencyCounter2);
  return true;
}

let result = same([1, 2, 3, 2], [9, 1, 4, 4]);
console.log(result);

👩🏻‍🌾 Coding Exercise 1: Frequency Counter - validAnagram

두 개의 문자열이 주어지면 두 번째 문자열이 첫 번째 문자열의 아나그램인지 확인하는 함수를 작성합니다. 

Examples:
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

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

Time Complexity - O(n)

👩🏻‍🌾 실습 - Refactor version O(N)

function validAnagram(a, b) {
  if (a.length !== b.length) {
    return false;
  }

  const lookup = {};

  for (let i = 0; i < a.length; i++) {
    let letter = a[i];
    lookup[letter] ? (lookup[letter] += 1) : (lookup[letter] = 1);
  }
  console.log(lookup);
  for (let i = 0; i < b.length; i++) {
    let letter = b[i];
    if (!lookup[letter]) {
      return false;
    } else {
      lookup[letter] -= 1;
    }
  }
  console.log(lookup);

  return true;
}

👩🏻‍🌾 Coding Exercise 3: Frequency Counter - sameFrequency

동일 주파수라는 함수를 작성합니다. 
두 개의 양의 정수가 주어지면 두 숫자의 자릿수가 같은지 확인합니다.
Time: O(N)

Sample Input:
sameFrequency(182,281) // true
sameFrequency(34,14) // false
sameFrequency(3589578, 5879385) // true
sameFrequency(22,222) // false

👩🏻‍🌾 실습 - Refactor version O(N)

function sameFrequency(a, b) {
  // good luck. Add any arguments you deem necessary.

  //a,b 는 숫자이기 때문에 split을 사용해 배열화 시킨다.
  a = (a + "").split("");
  b = (b + "").split("");

  /* 강의를 보니 문자열로 변환하는 toString방법도 있다.

      //num1, num2를 문자열로 바꿔 str1, str2에 할당한다.
    const str1 = num1.toString();
    const str2 = num2.toString();
  */

  //나머지 방법은 basic version과 같다.
  if (a.length != b.length) return false;
  const check = [];
  for (let i = 0; i < a.length; i++) {
    let letter = a[i];
    // 존재하면 1 추가 없으면 1로 초기화
    check[letter] ? (check[letter] += 1) : (check[letter] = 1);
  }
  for (let i = 0; i < b.length; i++) {
    let letter = b[i];
    if (!check[letter]) return false;
    else {
      check[letter] -= 1;
    }
  }
  return true;
}

👩🏻‍🌾 sameFrequency 솔루션

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

👩🏻‍🌾 Coding Exercise 4: Frequency Counter / Multiple Pointers - areThereDuplicates

변수 개수의 인수를 허용하고 전달된 인수 중 중복된 인수가 있는지 
확인하는 기능인 areThereDuplicates를 구현합니다. 
주파수 카운터 패턴 또는 다중 포인터 패턴을 사용하여 이 문제를 해결할 수 있습니다.

Examples:

areThereDuplicates(1, 2, 3) // false
areThereDuplicates(1, 2, 2) // true 
areThereDuplicates('a', 'b', 'c', 'a') // true 
Restrictions:

Time - O(n)

Space - O(n)

👩🏻‍🌾 실습 - Refactor version O(N)

// 전개구문 ... 사용하기 
function areThereDuplicates(...arr) {
  let check = [];
//순회 시작
  for (let i = 0; i < arr.length; i++) {
    //방법은 매우 똑같다.
    let letter = arr[i];
    check[letter] ? (check[letter] += 1) : (check[letter] = 1);
    // 1보다 클 경우 바로 return을 해서 종료
    if (check[letter] > 1) return true;
  }
  return false;
}

전개 구문을 사용하면 배열이나 문자열과 같이 반복 가능한 문자를 0개 이상의 인수 (함수로 호출할 경우) 또는 요소 (배열 리터럴의 경우)로 확장하여, 0개 이상의 키-값의 쌍으로 객체로 확장시킬 수 있습니다.

👩🏻‍🌾 areThereDuplicates 솔루션 (빈도 수 세기)

function areThereDuplicates() {
  let collection = {}
  for(let val in arguments){
    collection[arguments[val]] = (collection[arguments[val]] || 0) + 1
  }
  for(let key in collection){
    if(collection[key] > 1) return true
  }
  return false;
}

👩🏻‍🌾 areThereDuplicates 솔루션 (다중 포인터)

function areThereDuplicates(...args) {
  // Two pointers
  args.sort((a,b) => a > b);
  let start = 0;
  let next = 1;
  while(next < args.length){
    if(args[start] === args[next]){
        return true
    }
    start++
    next++
  }
  return false
}

👩🏻‍🌾 areThereDuplicates One Liner 솔루션

function areThereDuplicates() {
  return new Set(arguments).size !== arguments.length;
}

💻 Source

• ✏️ Best JavaScript Data Structures & Algorithms Course by Udemy, last updated January 2022, accessed April 5, 2023 - https://www.udemy.com/
• ⌨️ reference gitHub - https://github.com/seunghyun0522/JavaScript-Algorizms-Data-Structure