LeetCode 1268. Search Suggestions System

2019-12-04 1ilsangProblem Solving

searchWord의 접두사를 뽑아내 해당 접두사로 시작할 수 있는 products 배열의 값을 사전순으로 최대 3개 뽑아내는 문제다. 이 문제는 두 가지 방법으로 풀 수 있다. 하나는 트라이를 사용하여 직접 다 구현해 주는 것이고 두 번째는 filter 메서드를 사용해 뽑아내는 것이다. 두 가지 코드를 모두 소개해보려고 한다.

class Trie {
  TrieNode = class {
    constructor() {
      this.isEnd = false;
      this.value = '';
      this.next = new Map();
    }
  };

  constructor() {
    this.root = new this.TrieNode();
  }

  add(str) {
    let tmpNode = this.root;

    for (let i = 0; i < str.length; i++) {
      if (!tmpNode.next.has(str[i])) tmpNode.next.set(str[i], new this.TrieNode());
      tmpNode = tmpNode.next.get(str[i]);
    }

    tmpNode.isEnd = true;
    tmpNode.value = str;
  }

  find(node, list) {
    if (node.isEnd) {
      if (list.length < 3) list.push(node.value);
      else return;
    }
    if (node.next.size === 0) return;

    for (const key of node.next.keys()) {
      if (node.next.has(key)) this.find(node.next.get(key), list);
      if (list.length === 3) break;
    }
  }
}

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
const suggestedProducts = (products, searchWord) => {
  const ret = [];
  const trie = new Trie();

  const pList = products.slice().sort();
  pList.forEach(e => trie.add(e));

  let tmpTrie = trie.root;

  for (let i = 0; i < searchWord.length; i++) {
    const tmpList = [];
    const key = searchWord[i];

    if (!tmpTrie.next.has(key)) {
      ret.push(...new Array(searchWord.length - i).fill([]));
      break;
    }

    trie.find(tmpTrie.next.get(key), tmpList);
    tmpTrie = tmpTrie.next.get(key);
    ret.push(tmpList);
  }

  return ret;
};

첫 번째는 Trie 를 사용하는 코드다.

여기서 중요한 점은 products.sort() 를 해주어야 한다는 점인데, next를 Map 객체로 관리하고 있기 때문에 사전순으로 정렬해 순서대로 트라이에 add 해주어야 한다.(자바스크립트에서 맵은 삽입 순서를 지킨다 - MDN; A Map object iterates its elements in insertion order.)

트라이의 add 함수를 살펴보면 현재 문자열을 key 로 잡아 맵 객체에 존재다면 get으로 땡겨오고 아니면 new로 링크를 걸어준다.(링크드 리스트 생각)

그 다음 find 를 하기 전에 searchWord의 접두사가 트라이에 존재하는지 확인한다.(tmpTrie.next.has(key)) 여기서 해당 접두사가 존재하지 않는다는 것은 그 밑의 모든 문자열이 없다는 뜻이므로(순차적으로 들어가므로 접두사가 없으면 존재하지 않는 문자다) 빈 배열로 채운 다음에 포문을 끝내버린다. 이 가지치기를 통해 속도를 확 줄일 수 있다.

그 다음 find를 통해 맵 객체의 모든 key 를 순회하며 isEnd 를 만날 때마다 인자로 받아온 list에 push해준다.(call by reference`) 만약 3개가 다 차면 재귀를 탈출하고 아니면 계속해서 연결된 모든 맵 객체를 순회한다.

find 과정이 끝나면 노드를 다음 노드로 넘기고 인자로 넘겼던 tmpList를 반환할 ret 배열에 push 해준다.

조금 복잡해 보일수도 있지만 링크드 리스트라고 생각하고 노드의 next 만 잘 따라가면 해결할 수 있는 문제다.

다음은 훨씬 간편하게 풀 수 있는 filter 코드다.

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
const suggestedProducts = (products, searchWord) => {
  const n = searchWord.length;
  if (n < 1) return [];

  let list = products.slice().sort();
  const ret = [];

  for (let i = 0; i < n; i++) {
    list = list.filter(e => e[i] === searchWord[i]);
    ret.push(list.slice(0, 3));
  }

  return ret;
};

위와 같이 필터를 사용하게 될 경우 단어 하나씩 비교해가며 살아남는 리스트를 재할당해주고 3개 만큼만 뽑아서 푸쉬하면 끝나버린다. SO SIMPLE!

심지어 얘는 100ms 다 -_-;

트라이 공부한다 생각하고 트라이로도 구현해보자.

그럼 이만!