[JavaScript] Frequency Counter

OROSY·2021년 5월 27일

Algorithms

목록 보기

25/38

Frequency Counter

Udemy에서 새롭게 강의를 듣기 시작했다. 최근 Wecode 사전 스터디 모임에 이야기를 나누었을 때, 커리큘럼 시작 전에 추천하는 컴퓨터 공학 지식 중에 네트워크와 자료구조가 있었다.

실제로 Leetcode에서 문제를 풀면서 자료구조 관련 문제가 나오게 되면 손도 못대게 되는 상황이 많이 발생하였다. 이후로는 알고리즘을 풀어야겠다는 의지도 많이 사라졌다. 포기와 유보는 다르기에 잠시 알고리즘 풀이를 유보하면서 다른 공부를 하면서 고민을 하였다.

때마침 사전 스터디에 얘기가 나와서 알고리즘과 자료구조를 본격적으로 배워봐야겠다고 생각했다. 아무튼 한동안 블로그에는 알고리즘과 관련한 글을 위주로 포스팅을 할 예정이다.

Same

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)

Same은 두 개의 배열을 인수로 받는 함수이다. 첫번째 배열의 모든 value의 제곱수가 두번째 배열과 일치하면 true를 반환한다. value의 빈도수도 일치해야한다.

Solution (1)

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) // nested loops
    if (correctIndex === -1) {
      return false;
    }
    arr2.splice(correctIndex, 1);
  }
  return true;
}

위와 같이 푸는 방법도 있다. 실제로 이처럼 푸는 것도 쉬운 일은 아니라고 생각한다. 그러나 이 방법은 Big O가 O(n²)이기 때문이다. 그러므로 시간복잡도 면에서 피해야할 코드인 것이다.

Solution (2) - Refactored

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

위 풀이는 시간복잡도가 O(n)으로 nested loops가 없기 때문에 가능한 것이다. 복잡해보이지만, 실제로 코드를 찬찬히 뜯어보면 그렇게 복잡하지만은 않다. 배열의 value인 숫자들을 객체 데이터로 넣고 그 데이터의 value 값을 숫자로 준다.

frequencyCounter1의 key의 제곱값이 frequenycyCounter2의 key 값과 일치하는지 그리고 그 빈도수가 일치하는지를 확인해주면 되는 논리로 진행되는 코드이다.

OR operator와 Nullish coalescing operator

실제로 아래 코드를 처음 봤을 때는 이해를 하지 못했다. 논리연산자인 ||를 아직 제대로 이해하지 못했었기 때문이다. 이번 기회에 해당 내용을 정리해보려 한다.

frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1; // 1

const baz = 0 ?? 42;
console.log(baz) // 42

논리 연산자 중 OR operator(||)는 왼쪽이 false인 경우, 오른쪽의 값을 리턴한다. 처음에는 값이 undefined이기 때문에 초기값을 0으로 주어야만 숫자가 더해지기 때문에 꼭 위와 같이 코드를 작성해주어야 한다.

다만, 여기에 더해서 falsy 한 값(0, '', NaN, null, undefined) 모두를 false로 간주하기 때문에 오른쪽인 0을 리턴한다. 이를 해결하기 위한 연산자가 널 병합 연산자(??)이다.

frequencyCounter1[val] = (frequencyCounter1[val] ?? 0) + 1; // 1

const baz = 0 ?? 42;
console.log(baz) // 0

Nullish coalescing operator, 널 병합 연산자(??)는 왼쪽 피연산자가 null 또는 undefined일 때 오른쪽 피연산자를 반환하고, 그렇지 않으면 왼쪽 피연산자를 반환하는 논리 연산자이다.

validAnagram

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

이번에는 또 다른 예제이다. Anagram이라는 영어권에서는 직접 쓰는 단어이다. 사용된 스펠링이 같은 단어를 의미한다. 첫번째와 두번째 인자로 들어오는 string이 순서만 다르고 같은 수의 알파벳이 사용되면 true를 반환하는 함수를 만들면 된다.

조건은 모두 소문자 알파벳으로 구성되어 있으며, 시간복잡도는 O(n)이다.

Solution (1)

function validAnagram(str1, str2){
  // add whatever parameters you deem necessary - good luck!
    if (str1.length !== str2.length) {
    return false;
  }
  const anagramStr1 = {};
  const anagramStr2 = {};
  for (let val of str1) {
    anagramStr1[val] = (anagramStr1[val] || 0) + 1;
  }
  for (let val of str2) {
    anagramStr2[val] = (anagramStr2[val] || 0) + 1;
  }
  for (let key in anagramStr1) {
    if (anagramStr1[key] !== anagramStr2[key]) {
      return false;
    }
  }
  return true;
}

이처럼 위의 예제들과 마찬가지로 객체로 데이터에 넣어서 비교하는 방식으로 풀이를 진행하였다. 강의를 보기 전에 풀이를 한 것인데 시간복잡도도 O(n)이고 이해하기 쉽게 풀이를 한 것 같다. 아래에는 강의에서 풀이를 진행한 코드이다.

Solution (2) - Udemy

function validAnagram(str1, str2){
  // add whatever parameters you deem necessary - good luck!
    if (str1.length !== str2.length) {
    return false;
  }
  const lookup = {};
  
  for (let i = 0; i < str1.length; i++) {
    let letter = str1[i];
    // if letter exists, increment, otherwise set to 1
    lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
  }
  for (let i = 0; i < str2.length; i++) {
    let letter = str2[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;
}