[자료구조와 알고리즘] 유데미 강의 "JavaScript 알고리즘 & 자료구조 마스터클래스" 정리(섹션 5: 문제 해결 패턴)

섹션 5: 문제 해결 패턴

📌 빈도수 세기 패턴 (Frequency Counters)

[1, 2, 3], [1, 4, 9] 왼쪽 배열 요소의 제곱이 오른쪽 배열 요소에 딱 맞게 있으면 true, 그렇지 않으면 false를 반환하는 문제

indexOf 메서드가 for문 안에 있는 방식의 풀이 코드는 O(n^2) 시간 복잡도를 가진다. indexOf 메서드가 O(n)의 시간 복잡도를 가지고 있어서 중첩 for문과 같은 조건이 되어버리기 때문이다. 따라서 for문 안에서 indexOf  메서드를 사용하는 코드 대신에 for문을 여러 번 사용하더라도 반복문이 중첩되지 않도록 하는 것이 성능에 유리하다. 또한 배열의 경우 객체(배열 요소는 키, 동일 배열 요소의 개수는 값)로 만들면 O(1)의 시간 복잡도로 필요한 요소에 접근이 가능해진다.

🤔 O(n^2)을 순진한 접근법이라고 표현하고 있었다.

// indexOf 메서드 코드 예제
let arr1 = [1, 2, 3]
let arr2 = [1, 4, 9]
arr2.indexOf(arr1[0] ** 2) // arr2 배열의-인덱스가 아닌-값을 왼쪽 부터 찾아가는 방식이기 때문에 O(n)

 

✔ Anagram

단어나 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 것을 애너그램이라고 한다. 이 문제는 second가 first의 애너그램인지를 묻고 있다.

function validAnagram(first, second) {
  if (first.length !== second.length) return false;

  const lookup = {};

  for (let i in first) {
    lookup[first[i]] = lookup[first[i]] + 1 || 1;
    // 강의 예제에서는 삼항 연산자를 사용하고 있었다. 코드는 아래와 같다.
    // 각 항에 대입 연산자를 사용하고 있음을 주의 깊게 봤다.
    // lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
  }

  for (let i = 0; i < second.length; i++) {
    if (!lookup[second[i]]) return false; // second의 문자가 lookup 객체에 없거나 값이 0이면 false
    lookup[second[i]]--;
  }

  return true;
}