[프로그래머스] 60060 가사 검색 - 자바스크립트

문제

코딩테스트 연습 - 가사 검색

 

알고리즘 & 자료구조

트라이(Trie)

 

로직

const forwardRoot = new Map();
const backwardRoot = new Map();

정방향, 역방향 트라이(trie) root를 생성합니다.

각 root는 문자열의 길이를 key, 트라이를 value로 하는 Map 객체입니다.

root를 Map으로 표현하므로써 문자열의 길이로 트라이에 접근하여 더 효율적으로 문제를 해결할 수 있습니다.

 

words.forEach((word) => {
  insertTrie(word, forwardRoot);
  insertTrie(word.reverse(), backwardRoot);
});

주어진 단어들을 트라이에 삽입합니다.

insertTrie 함수는 아래와 같습니다.

 

function Node() {
  this.count = 0;
  this.child = new Map();
}

function insertTrie (word, root) {
  if (!root.has(word.length)) {
    root.set(word.length, new Node());
  }
  
  let node = root.get(word.length);

  for (const ch of word) {
    if (!node.child.has(ch)) {
      node.child.set(ch, new Node());
    }
    node.count++;
    node = node.child.get(ch);
  }
};

만약 각 root에 해당 단어의 길이 key가 없다면 { 단어의 길이: new Node() } 형태의 데이터를 추가합니다.

해당 key의 node들을 순회하며 단어의 각 문자들을 부모 node의 child 프로퍼티에 삽입합니다. 

이때, 순회하는 동시에 각 node의 count 프로퍼티에 +1 합니다.

• count 프로퍼티는 해당 node 이후 만들어질 수 있는 모든 단어의 수를 말합니다.

 

queries.forEach((query, i) => {
  answer[i] = (query[0] !== '?')
    ? searchTrie(query, forwardRoot)
    : searchTrie(query.reverse(), backwardRoot);
});

주어진 쿼리들을 트라이에 검색합니다.

searchTrie 함수는 아래와 같습니다.

 

function searchTrie (query, root) {
  if (!root.has(query.length)) {
    return 0;
  }

  let node = root.get(query.length);

  for (const ch of query) {
    if (ch === '?') {
      return node.count;
    }
    if (!node.child.has(ch)) {
      return 0;
    }
    node = node.child.get(ch);
  }
};

먼저 root에 해당 쿼리의 길이 key가 있는지 확인하고, 없다면 0을 반환합니다.

해당 key의 node들을 순회하며 쿼리의 각 문자들이 있는지 확인하고, 없다면 0을 반환합니다.

쿼리의 '?' 이전까지의 문자들이 모두 있다면 해당 node의 count 프로퍼티를 반환합니다.

 

코드

⏱ 시간 복잡도 :  O(nlogn)

function Node() {
  this.count = 0;
  this.child = new Map();
}

function insertTrie (word, root) {
  if (!root.has(word.length)) {
    root.set(word.length, new Node());
  }
  
  let node = root.get(word.length);

  for (const ch of word) {
    if (!node.child.has(ch)) {
      node.child.set(ch, new Node());
    }
    node.count++;
    node = node.child.get(ch);
  }
};

function searchTrie (query, root) {
  if (!root.has(query.length)) {
    return 0;
  }

  let node = root.get(query.length);

  for (const ch of query) {
    if (ch === '?') {
      return node.count;
    }
    if (!node.child.has(ch)) {
      return 0;
    }
    node = node.child.get(ch);
  }
};

function solution(words, queries) {
  String.prototype.reverse = function () {
    return this.split('').reverse().join('');
  };

  const forwardRoot = new Map();
  const backwardRoot = new Map();

  words.forEach((word) => {
    insertTrie(word, forwardRoot);
    insertTrie(word.reverse(), backwardRoot);
  });

  const answer = [];

  queries.forEach((query, i) => {
    answer[i] = (query[0] !== '?')
      ? searchTrie(query, forwardRoot)
      : searchTrie(query.reverse(), backwardRoot);
  });

  return answer;
}

 

리뷰

트라이는 한번도 사용해본적 없지만, 해당 문제를 읽고 트라이를 사용해야 한다는 것을 알았다.

정방향, 역방향 트라이를 각각 생성하는 방법 또한 떠올렸지만 효율성에서 자꾸만 틀렸다.

결국 다른 사람의 해결 방법을 참고했고, 각 단어의 길이별로 트라이를 생성하는 효율적인 방법을 알게되었다.

해당 방법은 정방향, 역뱡항 root node에 100001개의 트라이를 가진 배열을 정의하여 각 인덱스를 문자의 길이로 이용하는 방법이었는데, 이는 메모리 효율이 떨어진다 생각하여 배열이 아닌 Map 자료구조를 사용하여 문자 길이별 트라이를 동적으로 생성하도록 변형했다.

트라이를 문제에 처음 적용해보아 매우 유익했던 문제였다.