[프로그래머스] 가사 검색

2020 카카오 블라인드 채용 코딩 테스트 문제입니다.

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

문제 확인

 

트라이를 활용하는 문제입니다.

트라이 (컴퓨팅)

 

풀이

 

트라이의 가지를 알파벳에 대하여 만듭니다. 

 

와일드카드 문자 ? 는 조건에 따라 접두사, 접미사에서만 나오므로 역순으로 읽은 문자열에 대하여 트라이를 하나 더 생성합니다.

 

와일드카드 문자 특징은 길이가 1로 고정되어 있으므로 각 문자열의 길이를 map 컨테이너를 활용하여 구분할 수 있도록 합니다. map을 사용하지 않고 Trie *list[10001]을 사용할 수 있지만 map 컨테이너를 활용하는 것이 조금 더 빠르며 메모리 사용량이 더 적습니다.

 

최종 구조는 map<int(문자열 길이), Trie*(문자열 길이에 해당하는 문자열들의 트라이 루트>가 됩니다.

 

쿼리 접근 시 처음 문자가 ? 가 아니라면 일반 map, ?라면 reverse map에 접근하여 쿼리를 처리하면 됩니다.

 

코드

#include <string>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
 
 
typedef struct Trie {
    bool finish = 0;   
    int count = 0;
    Trie* next[26] = { 0 };   
    
    void insert(string &key) {
        int n = key.size();
        Trie* cur_node = this;
        for (auto c : key) {
            cur_node->count++;
 
            if (cur_node->next[c - 'a'] == NULL)
                cur_node->next[c - 'a'] = new Trie();
            cur_node = cur_node->next[c - 'a'];
        }
        cur_node->count++;
        cur_node->finish = true;
    }
    int find(string & key) {
        int n = key.size();
        Trie* cur_node = this;
        for (auto c : key) {
            if (!cur_node) return 0;
            else if (c != '?')
                cur_node = cur_node->next[c - 'a'];
            else
                return cur_node->count;
        }
        return cur_node ? 1 : 0;
    }
}Trie;
 
 
 
vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    map<int, Trie*> list, rev_list;
 
    for (auto &t : words) {
        int size = t.size();
        string rev_t = t;
        reverse(rev_t.begin(), rev_t.end());
 
        auto pos = list.find(size);
        if (pos == list.end()) {
            Trie *t_trie = new Trie(), *rev_t_trie = new Trie();
            t_trie->insert(t); 
            list.emplace_hint(pos, size, t_trie);
 
            rev_t_trie->insert(rev_t);
            rev_list[size] = rev_t_trie;
        }
        else {
            pos->second->insert(t);
            rev_list[size]->insert(rev_t);
        }
    }
    for (auto &qury : queries) {
        int size = qury.size();
        if (qury[0] != '?') {
            auto iter = list.find(size);
            if (iter != list.end()) 
                answer.push_back(iter->second->find(qury));
            else 
                answer.push_back(0);
            
        }
        else {
            reverse(qury.begin(), qury.end());
            auto iter = rev_list.find(size);
            if (iter != rev_list.end()) 
                answer.push_back(iter->second->find(qury));
            else 
                answer.push_back(0);
        }
    }
    return answer;
}
int main() {
    solution({ "frodo", "front", "frost", "frozen", "frame", "kakao" }, { "frodo", "????o", "fr???", "fro???", "pro?" });
}
/*
["frodo", "front", "frost", "frozen", "frame", "kakao"], ["fro??", "????o", "fr???", "fro???", "pro?"]
*/

정확성 테스트

테스트 1 〉	통과 (0.18ms, 3.96MB)
테스트 2 〉	통과 (0.06ms, 3.96MB)
테스트 3 〉	통과 (0.09ms, 3.97MB)
테스트 4 〉	통과 (0.08ms, 3.96MB)
테스트 5 〉	통과 (0.06ms, 3.97MB)
테스트 6 〉	통과 (0.10ms, 3.96MB)
테스트 7 〉	통과 (1.06ms, 5.28MB)
테스트 8 〉	통과 (0.47ms, 4.33MB)
테스트 9 〉	통과 (1.01ms, 5.17MB)
테스트 10 〉	통과 (1.09ms, 5.26MB)
테스트 11 〉	통과 (0.43ms, 4.34MB)
테스트 12 〉	통과 (1.08ms, 5.09MB)
테스트 13 〉	통과 (4.67ms, 10.6MB)
테스트 14 〉	통과 (2.13ms, 6.58MB)
테스트 15 〉	통과 (4.26ms, 10.2MB)
테스트 16 〉	통과 (4.65ms, 10.9MB)
테스트 17 〉	통과 (2.03ms, 6.41MB)
테스트 18 〉	통과 (4.49ms, 10.3MB)

효율성 테스트

테스트 1 〉	통과 (83.26ms, 119MB)
테스트 2 〉	통과 (186.24ms, 219MB)
테스트 3 〉	통과 (139.56ms, 205MB)
테스트 4 〉	통과 (181.29ms, 233MB)
테스트 5 〉	통과 (284.53ms, 437MB)

채점 결과

정확성: 25.0

효율성: 75.0

합계: 100.0 / 100.0