프로그래머스 LEVEL 4(가사 검색)

사용 언어 : javascript
해결 날짜 : 2023-05-23
해결 방법 :
- Trie 자료구조를 활용해 문제 해결
  - 정방향 단어(abc??, …)와 역방향 단어(??cba, …)를 따로 처리하기 위해 Trie 2개 생성
  - words를 돌며 정방향 word와 역방향 word를 각각 trie, reverseTrie에 insert
    - 이 때 단어에 끝으로 가는 모든 노드에 (총 단어 길이, 개수) 쌍을 추가
  - queries를 돌며 해당 query에 부합하는 words를 find

회고 :

처음에 작성한 코드

class Node {
  constructor(value = '') {
    this.value = value;
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(str) {
    let current = this.root;

    [...str].forEach((c) => {
      if (!current.children.has(c)) {
        current.children.set(c, new Node(current.value + c));
      }
      current = current.children.get(c);
    });

    current.isEnd = true;
  }

  find(str, i, node, arr = []) {
    if (str.length === node.value.length && node.isEnd) {
      arr.push(node.value);
    }

    if (str.length <= i) return;

    if (str[i] === '?') {
      for (const [key, value] of node.children) {
        this.find(str, i + 1, value, arr);
      }
    } else {
      if (node.children.has(str[i])) {
        this.find(str, i + 1, node.children.get(str[i]), arr);
      }
    }

    return arr.length;
  }
}

function solution(words, queries) {
  const trie = new Trie();

  words.forEach((word) => trie.insert(word));

  return queries.map((query) => trie.find(query, 0, trie.root));
}

정확성 테스트는 전부 통과했으나 효율성 테스트에서 시간 초과 및 런타임 에러가 발생했다…
queries에 중복이 포함될 수 있기에 이미 체크했던 쿼리에 대해서는 map에서 가져오도록 변경하였더니 효율성 테스트 두 개를 통과했다.
```
return queries.map((query) => {
  if (!map.has(query)) {
    map.set(query, trie.find(query, 0, trie.root));
  }

  return map.get(query);
});
```
런타임 에러가 발생하는 걸 보니 재귀를 사용하면 안될 것 같아 Trie를 ?로 시작하는 단어와 ?로 끝나는 단어로 구분하여 생성하고, 단어를 삽입할 때 단어에 끝으로 가는 모든 노드에 (총 단어 길이, 개수) 쌍을 추가해줌으로 문재를 해결했다.

코드

class Node {
  constructor(value = '') {
    this.children = new Map();
    this.count = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(str) {
    let current = this.root;
    current.count.set(
      str.length,
      !current.count.has(str.length) ? 1 : current.count.get(str.length) + 1,
    );

    [...str].forEach((c) => {
      if (!current.children.has(c)) {
        current.children.set(c, new Node(current.value + c));
      }
      current = current.children.get(c);
      current.count.set(
        str.length,
        !current.count.has(str.length) ? 1 : current.count.get(str.length) + 1,
      );
    });
  }

  find(str, node) {
    for (const c of [...str]) {
      if (c === '?') {
        return node.count.get(str.length) || 0;
      }

      if (!node.children.has(c)) {
        return 0;
      }

      node = node.children.get(c);
    }
  }
}

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

  const trie = new Trie();
  const reverseTrie = new Trie();

  words.forEach((word) => {
    trie.insert(word);
    reverseTrie.insert(word.reverse());
  });

  return queries.map((query) =>
    query[0] === '?'
      ? reverseTrie.find(query.reverse(), reverseTrie.root)
      : trie.find(query, trie.root),
  );
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges