가사 검색

Description

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

Input

가사 단어 제한사항
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??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

Example

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

Code

#include <bits/stdc++.h>

using namespace std;

struct Trie{
    bool leaf;
    int count;
    Trie* next[26];

    Trie(){
        leaf = false;
        count = 1;
        fill(next, next+26, nullptr);
    }
    ~Trie(){
        for(int i=0; i<26; i++)
            if(next[i]) delete next[i];
    }

    void insert(const char* key ){
        if(*key=='\0'){
            leaf = true;
            return;
        } //base case

        int next_char_idx = *key - 'a';
        if(next[next_char_idx] == nullptr)
            next[next_char_idx] = new Trie();
        else next[next_char_idx]->count++;
        next[next_char_idx]->insert(key+1);
    }

    int find(const char* key){
        int curr = *key - 'a';
        if(*key == '?'){
            int tmp = 0;
            for (int j=0; j<26; j++){
                if(next[j] != nullptr)
                    tmp += next[j]->count;
            }
            return tmp;
        }
        if(next[curr] == nullptr) return 0;
        if(*(key+1) == '?') return next[curr]->count;
        return next[curr]->find(key+1);
    }
};


vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer (queries.size(), 0);

    Trie* trie [100001];
    Trie* r_trie [100001];

    for(string str : words){
        int l = str.length();
        if(!trie[l]) trie[l] = new Trie();
        trie[l]->insert(str.c_str());

        reverse(str.begin(), str.end());
        if(!r_trie[l]) r_trie[l] = new Trie();
        r_trie[l]->insert(str.c_str());
    }
    int i=0;
    for (string query : queries){
        int l = query.length();
        if (query[0] == '?'){
            reverse(query.begin(), query.end());
            if(!r_trie[l]){
                i++;
                continue;
            }
            answer[i++] = r_trie[l]->find(query.c_str());
        }else{
            if(!trie[l]){
                i++;
                continue;
            }
            answer[i++] = trie[l]->find(query.c_str());
        }
    }
    return answer;
}

Thoughts

이 문제는 2020 카카오 블라인드채용 1차의 4번 문제이며 정답률은 정확성: 34.4% 효율성: 0.8%를 기록한 지원자 대부분이 통과하지 못했던 문제이다.
문제를 읽고 해석하는데에는 큰 어려움이 없다. 오히려 간단하지만 막상 어떤식으로 구현해야할지 고민이 길었다.
제한사항을 보게되면 words길이와 queries길이가 최대 100,000개 씩으로, query하나씩 꺼내어 모든 word를 순회하는 iterative한 단순한 방법으로는 정확성은 통과할수 있지만 효율성에서 시간초과를 보게 된다. (처음에 나 역시 그렇게 구현했다.)

이 문제를 풀 수 있는 다양한 방법이 존재하겠지만, 문자열을 탐색하는데에 있어 굉장히 효율적인 자료구조인 Trie를 이용하면 매우 간단하게 풀 수 있다.
Trie 자료구조에 대한 자세한 내용은 조만간 자료구조 정리를 하면서 글을 기재할 때 포함해볼 계획이다.

위 그림을 보면 두가지 trie를 사용했는데 그 이유는, 접두사부터 시작하는 query인 경우 "????o"를 생각해보자.
접두사에서부터 ?가 있는 query는 앞이 아니라 뒤에서부터 word를 찾으면 되기 때문에, 단어의 뒤부터 담은 r_trie를 구현했다.
따라서 queries를 순회하면서 '?'가 접두사부터 시작하는지 접미사부터 체크하고, 접두사부터 시작하면 r_trie에서 단어 조회, 접미사부터 시작하면 trie에서 단어 조회를 하면 된다.

이렇게만 구현했더니 나는 효율성에서 모두 통과하지 못했다.
그래서 trie에서 단어를 조회하기 전에, 단어의 길이를 미리 체크할 수 있으면, 시간을 단축 할 수 있으므로, trie 배열을 만들어서 단어의 길이 별로 따로 구현하여, query.length()에 맞는 trie[query.length()]에서 단어를 조회하면된다.
이렇게해도 효율성을 몇개 통과하지 못하였다...

마지막으로 시도한 효율성 향상을 위한 방법은 바로 ?가 나오는 시점에 더이상 단어조회를 할 수 있지 않게 하는 방법이다.
query를 가지고 trie에서 조회를 하는 도중 관심 query의 char가 '?'인 순간이 되면 바로 그 자식 노드를 갈필요 없이 해당 노드의 count값을 바로 return하는 방법을 이용하면 시간을 더 줄일 수 있고, 이렇게 했더니 모든 효율성 테스트를 통과했다.

정리하자면,
어려운 문제인가? 아닌거 같다. 문제를 이해하는데에 아무런 막힘이 없을 것이다.
다만 '어떻게' 푸는지가 중요한 문제이다.
"이런 상황에서 trie자료구조를 써야겠다"라는 생각을 할 수 있으려면, 더 많은 경험과 특징 및 이해도를 높이는 것 뿐 다른 방법은 잘 모르겠다.
카카오 공식 해설에는 이분탐색 방법도 존재한다고 언급되어 있어 추후에 이분탐색을 이용한 풀이도 도전해볼 것이다.