가사 검색

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 > 반환하도록 solution 함수를 완성해 주세요.

가사 단어 제한사항

• words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
• 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
• 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
• 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

검색 키워드 제한사항

• queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
• 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
• 검색 키워드는 중복될 수도 있습니다.
• 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
• 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
  • 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
  • 반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

입출력 예

words	queries	result
["frodo", "front", "frost", "frozen", "frame", "kakao"]	["fro??", "????o", "fr???", "fro???", "pro?"]	[3, 2, 4, 1, 0]

입출력 예에 대한 설명

• "fro??"는 "frodo", "front", "frost"에 매치되므로 3입니다.
• "????o"는 "frodo", "kakao"에 매치되므로 2입니다.
• "fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4입니다.
• "fro???"는 "frozen"에 매치되므로 1입니다.
• "pro?"는 매치되는 가사 단어가 없으므로 0 입니다.

문제 풀이

1. Node클래스를 생성. 각 해당하는 문자의 갯수를 알기 위해서 count를 추가.
2. Trie클래스
   1. root는 new Node로 생성(root노드는 아무 문자열도 안가지고 있음.) -> "?????"같은 와일드 카드로만 구성된 경우에 사용
   2. insert과정에는, 최상위 노드부터 거쳐간 노드는 count를 ++해준다.
   3. search는 해당 문자를 찾으면, count를 반환한다.
3. solution 함수
   1. tries의 경우 words의 크기만큼 만들어 준다.(0,1은 사용 안함.)
   2. words를 tries 배열에 trie를 만들어서 넣어주는데, 정방향과 역방향 문자열을 tries[i][0],tries[i][1]에 각각 넣어준다.(와일드카드가 앞에있는지, 뒤에있는지 확인하고 사용함.)
   3. tries 배열을 처리하고, queries에 대해서 for문.
   4. queries[i]의 길이가 tries 배열에 없다면, answer에 0을 push.
   5. queries[i]가 모두 "?"으로 이루어져 있다면, tries[len][0]의 root의 count값을 push.
   6. queries[i][0]가 "?"가 아닌경우 -> tries[len][0]에서 search 후 return 값을 push.
   7. 나머지 경우(앞에서 "?"로 시작될 경우)에는 역순으로 문자열을 바꿔주고, tries[len][1]에서 search 후 return 값을 push.

class Node {
  constructor(value = "") {
    this.value = value;
    this.child = {};
    this.count = 0;
  }
}

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

  insert(string) {
    let currentNode = this.root;
    currentNode.count++;
    for (let i = 0; i < string.length; i++) {
      if (currentNode.child[string[i]] === undefined) {
        currentNode.child[string[i]] = new Node(currentNode.value + string[i]);
      }
      currentNode = currentNode.child[string[i]];
      currentNode.count++;
    }
  }

  search(str) {
    let currentNode = this.root;
    for (let i = 0; i < str.length; i++) {
      if (currentNode.child[str[i]]) {
        currentNode = currentNode.child[str[i]];
      } else {
        return 0;
      }
    }
    return currentNode.count;
  }
}

function solution(words, queries) {
  var answer = [];
  let tries = Array(100001);
  for (let i = 0; i < words.length; i++) {
    let word = words[i];
    let re = [...word].reverse().join("");
    let len = words[i].length;
    if (tries[len]) {
      tries[len][0].insert(word);
      tries[len][1].insert(re);
    } else {
      tries[len] = Array(2);
      tries[len][0] = new Trie();
      tries[len][1] = new Trie();
      tries[len][0].insert(word);
      tries[len][1].insert(re);
    }
  }

  for (let i = 0; i < queries.length; i++) {
    let query = queries[i];
    if (tries[query.length] === undefined) {
      answer.push(0);
      continue;
    }
    if ([...query].every(e => e === "?")) {
      let len = query.length;
      answer.push(tries[len][0].root.count);
    } else if (query[0] !== "?") {
      let len = query.length;
      let idx = query.indexOf("?");
      let target = query.slice(0, idx);
      answer.push(tries[len][0].search(target));
    } else {
      let re = [...query].reverse().join("");
      let len = query.length;
      let idx = re.indexOf("?");
      let target = re.slice(0, idx);
      answer.push(tries[len][1].search(target));
    }
  }

  return answer;
}