문제 설명

검색 키워드 제한사항

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

입출력 예

wordsqueriesresult
["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 입니다.

문제 풀이

정확성은 brute-force로 가능한데 효율성은 통과하지 못한다.
효율성을 통과하기 위해 Trie 자료구조를 사용하면 된다.

문제에 ‘?’ 가 앞이나 뒤에 올 수 있기 때문에,
Trie를 reverse하는 것도 추가해야 한다
크게 Trie가 2개 필요하다.

여러 단어를 매칭해야 되고 각 단어마다 길이가 각각 다르기 때문에 처리하기가 쉽지 않다.
그래서 각 Trie마다 고정 길이 Trie를 만들 필요가 있다.

총 Trie는 [앞뒤][문자길이] => [2][10001] 로 만들어서 풀면 된다.

Trie에 child 변수를 추가했는데
이 다음 node에 몇개가 있는지 파악하기 위해서 추가했다.
매칭할 때 더 밑에 안가고 cut할 수 있다.

소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

struct Trie {
    Trie* next[26];
    bool finish;
    int child;
};

Trie trie[2][10001];

Trie* newNode(){
    auto new_node = new Trie;
    memset(new_node->next, 0, sizeof(new_node->next));
    new_node->finish = false;
    new_node->child = 0;
    return new_node;
}

void insert(Trie* parent, const char* c){
    if (*c == '\0'){
        parent->finish = true;
        return;
    }
    
    ++parent->child;
    
    int i = *c - 'a';
    if (parent->next[i] == nullptr) {
        parent->next[i] = newNode();
    }
    insert(parent->next[i], c+1);
}

int match(Trie* parent, const char* c){
    if (parent == nullptr)  return 0;
    if (*c == '\0')         return parent->finish ? 1 : 0;
    
    int count = 0;
    if (*c == '?') {
        count = parent->child;
    } else {
        count = match(parent->next[*c - 'a'], c+1);
    }
    return count;
}

vector<int> solution(vector<string> words, vector<string> queries) {
    for(auto& word : words){
        int length = word.length();
        insert(&trie[0][length], word.c_str());
        
        string reverse_word = word;
        reverse(reverse_word.begin(), reverse_word.end());
        insert(&trie[1][length], reverse_word.c_str());
    }
    
    vector<int> answer = vector<int>(queries.size());
    
    for(int i = 0; i < answer.size(); ++i){
        auto& query = queries[i];
        int length = query.length();

        int count;
        if (query[0] != '?') {
            count = match(&trie[0][length], query.c_str());
        } else {
            string reverse_query = query;
            reverse(reverse_query.begin(), reverse_query.end());
            count = match(&trie[1][length], reverse_query.c_str());
        }
        answer[i] = count;
    }
    
    return answer;
}

문제 위치 – https://programmers.co.kr/learn/courses/30/lessons/60060