빈도수 세기 패턴

Daisy🌼·2022년 11월 14일

목록 보기

1/3

~~밀려드는 자료구조와 알고리즘에 휩쓸리는 중~~

예전부터 알고리즘 스터디를 하고 있었지만, 알고리즘이나 코딩테스트가 어렵게 느껴져서 꾸준히 하지 못했다. 그 결과 알고리즘 스터디 최약체가 되어버렸다.🙂 하지만 이제는 더이상 미룰 수 없기도 하고, 부실 공사는 언젠가 무너진다 는걸 알고 있기 때문에 지나온 시간이 부끄럽지만 다시 처음으로 돌아가 실력을 단단히 하기로 했다.

빈도수 세기 패턴

특정 문자열이나 배열이 주어졌을 때 빈도수를 체크해나가는 풀이 방식

대표 문제

두 배열이 주어질 때, 두 번째 배열의 모든 요소들이 첫 번째 배열의 모든 요소의 제곱에 대응할 경우 true를, 아니면 false를 리턴하는 함수 same을 작성하라.

🤔 naive solution

가장 naive한 방법은 첫 번째 배열의 요소를 순회하면서 두 번째 배열의 모든 요소와 비교하는 것이다.
즉 두 번째 배열에 첫 번째 배열 요소를 제곱한 값이 포함되어있는지 일일이 찾는다.
값이 있는지 확인하기 위해 indexOf(), includes()와 같은 배열 메서드를 사용할 수 있다.

indexOf(): 지정된 값이 배열에 들어있으면 값을 등장하는 첫 번째 인덱스를, 없으면 -1를 반환하는 메서드

includes(): 지정된 값이 배열에 들어있으면 true, 없으면 false를 반환하는 메서드

function same(arr1, arr2) {
  // 요소의 개수가 서로 다르면 무조건 false이므로 early return 해준다.
  if (arr1.length !== arr2.length) return false;

  for (let i = 0; i < arr1.length; i++) {
    const currentIndex = arr2.indexOf(arr1[i] ** 2);
    if (currentIndex === -1) return false;
    // 모든 요소들이 일대일로 대응하는지 여부를 확인해야하므로 확인된 요소는 지운다.
    arr2.splice(currentIndex, 1);
  }
  return true;
}

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) return false;

  for (let i = 0; i < arr1.length; i++) {
    const currentIndex = arr2.includes(arr1[i] ** 2);
    if (!currentIndex) return false;
    arr2.splice(currentIndex, 1);
  }
  return true;
}

하지만 indexOf()와 includes()의 시간 복잡도는 O(N)이므로, 이를 for문 안에서 실행하면 시간복잡도는 O(N^2)이 된다. 만약 입력받는 배열이 매우 크다면 문제를 해결하는 데 필요한 실행 횟수는 기하급수적으로 늘어난다.
이렇게 배열의 요소를 검색하는 메서드(find, findIndex, indexOf 등)는 for문 안에서 사용할 경우 큰 시간복잡도를 갖게 되므로 주의해야 한다.

😎 good solution

빈도수 세기 패턴의 핵심은 객체를 만들어 값의 빈도를 수집하는 것이다.
이렇게 하면 for문 안에서 또다시 배열을 검색하지 않아도 되므로 O(N^2)에서 O(N)으로 시간복잡도를 줄일 수 있다. (위의 시간 복잡도 차트를 보면 얼마나 획기적으로 시간 복잡도를 줄이는 것인지 알 수 있다!)

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) return false;

  // 빈 객체를 선언한다.
  const counter1 = {};
  const counter2 = {};

  // 배열을 순회하면서 배열의 요소: 요소의 개수와 같이 프로퍼티를 추가한다.
  for (let i of arr1) {
    if (!counter1[i]) {
      counter1[i] = 1;
    } else {
      counter1[i]++;
    }
  }

  for (let i of arr2) {
    if (!counter2[i]) {
      counter2[i] = 1;
    } else {
      counter2[i]++;
    }
  }

  // 객체를 순회한다.
  for (let key in counter1) {
    // in 연산자: 속성 in 객체
    if (!(key ** 2 in counter2)) return false;
    if (counter2[key ** 2] !== counter1[key]) return false;
  }
  return true;
}

여기서 in 연산자라는 것을 사용했는데, 이는 지정된 속성이 객체에 있는 속성인지 확인하는 연산자이다. 그런데 배열 매서드의 includes()처럼 존재 여부를 판별하는 연산자니까 시간복잡도가 O(N)이라고 생각했는데, 찾아보니까 자바스크립트에서 객체는 해시테이블처럼 작동한다고 한다. 따라서 검색의 시간 복잡도는 O(1)이라고 한다. 그리고 for...in 문과 헷갈리지 말자!

빈 객체에 값을 추가하는 for...of문은 아래와 같이 리팩토링 할 수도 있다. (어떤 게 좋은 지는 취향차이일지도?🤔 나는 습관적으로 직관적인 if문을 썼지만, 아래 코드를 한 번 이해하기만 하면 아래의 방법이 더 깔끔한 것 같다.)

for (let i of arr1) {
  // 값이 없으면 0으로 초기화하고 1을 더해주고, 있으면 기존의 값에 1을 더해준다.
  // 즉 if문 대신 단축 평가를 사용했다!
  conter1[i] = (counter1[i] || 0) + 1;
}

for (let i of arr2) {
  counter2[i] = (counter2[i] || 0) + 1;
}

연습 문제

두 개의 문자열이 주어질 때, 두 번째 문자열이 첫 번째 문자열의 애너그램인지 판별하는 함수 validAnagram을 작성하라.

🤔 나의 풀이

function validAnagram(str1, str2) {
  if (str1.length !== str2.length) return false;

  const counter1 = {};
  const counter2 = {};

  for (let i of str1) {
    counter1[i] = (counter1[i] || 0) + 1;
  }

  for (let i of str2) {
    counter2[i] = (counter2[i] || 0) + 1;
  }

  for (let key in counter1) {
    if (!(key in counter2)) return false;
    // 두 객체를 만들었기 때문에 속성값, 즉 빈도수를 직접 비교해서 바로 false를 리턴할 수 있다.
    if (counter1[key] !== counter2[key]) return false;
  }
  return true;
}

😎 다른 풀이

나의 풀이와 다른 점은, 빈 객체를 하나만 만들어 비교했다는 점이다.

function validAnagram(str1, str2) {
  if (str1.length !== str2.length) return false;

  const lookup = {};

  for (let i = 0; i < str1.length; i++) {
    let letter = str1[i];
    lookup[letter] ? (lookup[letter] += 1) : (lookup[letter] = 1);
  }

  for (let i = 0; i < str2.length; i++) {
    let letter = str2[i];
    if (!lookup[letter]) {
      return false;
    } else {
      lookup[letter] -= 1;
    }
  }
  return true;
}

코드를 조금 더 간결하게 하기 위해 아래와 같이 리팩토링 해보았다.
for...of문을 활용해 배열을 순회했고, 객체에 프로퍼티를 추가하는 반복문을 한 줄로 작성했다.

function validAnagram(str1, str2) {
  if (str1.length !== str2.length) return false;

  const lookup = {};

  for (let i of str1) {
    lookup[i] = (lookup[i] || 0) + 1;
  }

  for (let i of str2) {
    // (!lookup[i])는 i가 존재하지 않거나 lookup[i]의 값이 0인 경우
    if (!lookup[i]) {
      return false;
    } else {
      lookup[i] -= 1;
    }
  }
  return true;
}

정리

반복문 안에서 또다른 배열을 순차적으로 검색하는 경우, 효율성에 주의해야 한다.
빈도수 세기 패턴은 객체를 생성해 빈도수를 저장한 다음, 생성된 객체들의 키와 값을 사용한다.
빈도수 세기 패턴을 사용하기 위해서는 배열을 for...of문으로 순회해 객체에 프로퍼티를 추가하는 코드를 능숙하게 짜는 연습을 많이 해야될 것 같다.