programmers [C++] : 2020 KAKAO BLIND RECRUITMENT 가사검색

programmers.co.kr/learn/courses/30/lessons/60060

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

문제 설명

---

키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어  "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

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

 

접근 방법

---

처음에 간단하게 생각하고 선형 방식으로 코드를 작성했는데 효율성 1,2,3에서 통과하지 못했습니다. 고민을 해봐도 효율성 오답을 해결하지 못했습니다. 그래서 결국 해답을 보고 나서야 ㅠㅠ Trie 자료구조를 활용해야 한다는 것을 깨달았습니다...

종만북에는 설명이 되어있다니 종만북 가지고 계신 분은 참고하셔도 될 거 같아요! 

Trie 에 대한 설명은 아래 블로그 운영하시는 분이 자세히 설명을 잘해놔서 출처를 적어놓았습니다~

참고: jason9319.tistory.com/129

[자료구조]트라이(Trie)

잘못된 코드 [1] & 정답 풀이[2]

---

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

vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    
    for(int i=0;i<queries.size();i++){
        string query=queries[i];
        bool isfirst=false;
        int idx=0,cnt=0;
        for(int k=0;k<query.size();k++){
            if(k==0){
                if(query[k]=='?')isfirst=true;
            }
            else{
                if(isfirst==true&&query[k]!='?'){idx=k;break;}
                else if(isfirst==false && query[k]=='?'){idx=k;break;}
            }
        }
        
        for(int j=0;j<words.size();j++){
            if(words[j].size()!=query.size())continue;
            else{
                if(isfirst){
                    if(idx==0)cnt++;
                    else if(words[j].substr(idx).compare(query.substr(idx))==0)cnt++;
                }
                else{
                    if(words[j].substr(0,idx).compare(query.substr(0,idx))==0)cnt++;
                }
            }
        }
        answer.push_back(cnt);
    }
    return answer;
}

//Trie 사용
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
//Trie 자료구조 사용
struct Trie{
    Trie* next[26]; //26가지 알파벳에 대한 트라이
    bool finish; //끝나는 지점 표시
    int cnt;
    Trie() : finish(false), cnt(1){
        memset(next, 0, sizeof(next));
    }
    ~Trie(){
        for(int i = 0; i < 26; i ++){
            if(next[i]) delete next[i];
        }
    }
    
    void insert(const char* key){
        if (*key == '\0')
            finish = true;    //문자열이 끝나는 지점일 경우 표시
        else {
            int curr = *key - 'a';
            if (next[curr] == NULL)
                next[curr] = new Trie();    //탐색이 처음되는 지점일 경우 동적할당
            else next[curr]->cnt++;
            next[curr]->insert(key + 1);    //다음 문자 삽입
        }
    }
    
    int find(const char* key){
        int curr = *key - 'a';
        if(*key == '?'){
            int tmp = 0;
            for(int i = 0; i < 26; i++){
                if(next[i] != NULL) tmp += next[i]->cnt;
            }
            return tmp;
        }
        if(next[curr] == NULL) return 0;
        if(*(key+1) == '?') return next[curr]->cnt;
        return next[curr]->find(key+1);
    }
        
};

Trie *root[10001];
Trie *reroot[10001];
vector<int> solution(vector<string> words, vector<string> queries) {
    int wSize = words.size();
    int qSize = queries.size();
    vector<int> answer(qSize,0); //0으로 초기화
    
    for(auto &w : words){
        int size = w.size();
        
        const char *c = w.c_str();
        
        if(root[size] == NULL) root[size] = new Trie();
        root[size]->insert(c);
        
        string reversed = w;
        reverse(reversed.begin(),reversed.end());
        
        const char *r = reversed.c_str();
        if(reroot[size] == NULL) reroot[size] = new Trie();
        reroot[size]->insert(r);
    }
    
    int idx = 0;
    for(auto & q : queries){
        int size = q.size();
        if(q[size-1] == '?'){
            const char *c = q.c_str();
            if(root[size] == NULL) {idx++; continue;}
            else answer[idx] = root[size]->find(c);
        }
        else{
            string re = q;
            reverse(re.begin(),re.end());
            const char *r = re.c_str();
            
            if(reroot[size] == NULL){idx++; continue;}
            else answer[idx] = reroot[size]->find(r);
        }
        idx++;
    }
    return answer;
}

funny algorithm 0_<