[Programmers - lv04] 가사 검색 (C++/Python)

가사 검색

코딩테스트 연습 - 가사 검색

문제 설명

주어지는 words의 단어들을 quries로 찾아내는 문제.

quries에는 '?'라는 와일드 카드가 존재하고 ?는 모든 문자에 해당한다.

입출력 예

 

문제를 보자마자 Trie로 풀어야겠다는 생각에 예전 기억을 떠올리며 Trie 자료 구조를 이용하여 문제를 풀었지만, 효율성 테스트에서 막혔다. 가사검색 풀었던 친구에게 물어보니 reverse trie를 만들어서 해결하라는 말을 듣고, 문제를 통과했다. 

문제 풀이

소스코드 : C++

Trie 를 이용한 풀이

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

int cnt;
class Trie{
public:
    Trie *child[128];
    bool flag;

    Trie() : flag(false){
        for (int i = 0; i < 128; i++)
            child[i] = 0;
    }
    ~Trie(){
        for (int i = 0; i < 128; i++)
            if (child[i])
                delete child[i];
    }

    void insert(const char* key){
        if (!*key)
            flag = true;
        else{
            int next = *key;
            if (!child[next])
                child[next] = new Trie();
            child[next]->insert(key + 1);
        }
    }

    void search(const char *key){
        if (!*key) {
            if (this->flag)
                cnt++;
            return ;
        }
        int next = *key;
        if (child[next] == 0){
            if (*key == '?'){
                for (int i = 1; i < 128; i++)
                    if (child[i])
                        child[i]->search(key + 1);
                return ;
            }
            else 
                return ;
        }
        else
            child[next]->search(key + 1);
    }
};

vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    Trie *root = new Trie;
    for (auto w : words){
        const char *c = w.c_str();
        root->insert(c);
    }
    for (auto q : queries){
        const char *c = q.c_str();
        cnt = 0;
        root->search(c);
        answer.push_back(cnt);
    }
    return answer;
}
int main(){
    vector<string> words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
    vector<string> quries = {"fro??", "????o", "fr???", "fro???", "pro?"};

    for (auto ans : solution(words, quries))
        cout<<ans<<" ";
    
    return 0;
}

 

Trie와 Reverse Trie를 이용한 풀이

 

같이 스터디하는 인원 중 선형 탐색으로 풀이한 분이 있었는데, 효율성 테스트 1, 2, 3에서 걸려서 효율을 잡을 수 있는 부분에서 잡아서 작성해봤지만 효율성 테스트 1, 2, 3을 역시 통과하지 못 했다.

매우 마음에 드는 아이디어였는데 너무 아쉽다...

#include <string>
#include <vector>
#include <iostream>
using namespace std;

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

    for (int i = 0; i < qlen; i++) {
        string query = queries[i];
        string check = "";
        int start = 0, count = 0;   // ?가 시작되는 지점, ?의 개수
        bool flag = false;  // ? 가 나오기 시작했는지 안했는지
        bool qMark = true;  // 쿼리문이 ?가 포함 됐는지 안됐는지
        int cnt = 0;        // 해당 쿼리에 해당하는 워드의 개수
        for (int j = 0; j < query.size(); j++) {
            if (query[j] != '?') {  // query가 ?가 아니면 check에 누적
                check += query[j]; 
                qMark = false;
            }
            if (query[j] == '?' && !flag) { // query가 ?이고 처음 등장한다면
                start = j; 
                flag = true; 
            }
            // ?가 나온 적 있고, ?가 아닌 문자 이거나 마지막 문자일 때
            if ((flag && query[j] != '?') || (flag && j == query.size() - 1)) {
                if (start == 0) count = j;
                else
                    count = (j - start) + 1;
                flag = false;
            }
        }

        for (int j = 0; j < wlen; j++) {
            if (query.size() != words[j].size()) continue;  //
            if (qMark && query.size() == words[j].size()) {
                cnt++; 
                continue; 
            }
            string inc = "", exc = "";// ?  포함, ? 미포함
            if (start == 0) {   // 시작부분이 ?
                inc = words[j].substr(0, count);
                exc = words[j].substr(count);
            }
            else {  // 시작부분이 ? x
                inc = words[j].substr(start);
                exc = words[j].substr(0, start);
            }

            if ((exc.size() == check.size()) 
                    && ((check == exc) && (inc.size() == count)))
                cnt++;
        }
        answer.push_back(cnt);
    }

    return answer;
}