[C++, Python] Trie - 2020 카카오 : 가사 검색

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

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

 

1. Python

풀이

1. 우선 단순하게 글자 queries 와 words 글자 비교를 해서 풀었다

글자수가 다르면 continue, ?여도 continue

def solution(words, queries):
    answer = []
    for query in queries:
        cnt = 0
        for word in words:
            if len(query) != len(word): continue
            else :
                flag = True
                for i in range(len(query)):
                    if query[i] == '?': continue
                    elif query[i] != word[i]: 
                        flag = False
                        break
                if flag : cnt += 1
        answer.append(cnt)
    return answer

 

 

이렇게 풀면 정답은 다 맞는데 효율성에서 5개중 2개만 통과다.

채점 결과를 보면 정확성이 25점 만점, 효율성이 75점 만점이다.

그래서 정확성 25점에 효율성 75/5*2 = 30점해서 55점이다. 

 

 

2. Trie로 풀기

유튜브 주렁코드의 해설을 참고했다. 차근차근 설명을 잘해주신다.

전체 코드는 여기서 볼 수 있다.

 

class Node(object):
    def __init__(self, key):
        self.key = key #이전값
        self.remain_len = {} #terminal 까지 남은 문자열 길이
        self.children = {}
        
class Trie(object):
    def __init__(self):
        self.head = Node(None)
    
    def insert(self, string):
        curr_node = self.head
        
        #단어들의 남은 철자 갯수 저장해놓기
        remain_len = len(string)
        if remain_len in curr_node.remain_len:
            curr_node.remain_len[remain_len] += 1
        else:
            curr_node.remain_len[remain_len] = 1
            
        
        for chr in string:
            if chr not in curr_node.children:
                curr_node.children[chr] = Node(chr)
            
            curr_node = curr_node.children[chr]
            remain_len -= 1
            if remain_len in curr_node.remain_len:
                curr_node.remain_len[remain_len] += 1
            else:
                curr_node.remain_len[remain_len] = 1
    
    def search_cnt(self, string, qstMark_len):
        curr_node = self.head
        
        if qstMark_len + len(string) not in curr_node.remain_len:
            return 0
        
        for chr in string:
            if chr in curr_node.children:
                curr_node = curr_node.children[chr]
            else:
                return 0
            
        if qstMark_len in curr_node.remain_len:
            return curr_node.remain_len[qstMark_len]
        else:
            return 0
            
                
def solution(words, queries):
    t = Trie()
    inv_t = Trie() #거꾸로 
    for word in words:
        t.insert(word)
        inv_t.insert(word[-1::-1])

    answer = []
    for query in queries:
        #?시작
        if query[0] == '?':
            query = query[-1::-1] #거꾸로 뒤집기
            chrs = query.replace('?', '')
            qstMark_len = len(query) - len(chrs)
            answer.append(inv_t.search_cnt(chrs, qstMark_len))
            
        #알파벳 시작
        else:
            chrs = query.replace('?', '')
            qstMark_len = len(query) - len(chrs)
            answer.append(t.search_cnt(chrs, qstMark_len))
            
    return answer

결과

 

2. C++

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
 
struct Trie{
    Trie* next[26];
    int count;
    bool term;
    Trie() : term(false), count(1){
        memset(next, 0, sizeof(next));
    }
    ~Trie(){
        for (int i = 0; i<10; i++){
            if (next[i])
                delete next[i];
        }
    }
    void insert(const char* key){
        if (*key == '\0')
            term = true;
        else{
            int curr = *key - 'a';
            if (next[curr] == NULL)
                next[curr] = new Trie();
            else
                next[curr]->count++;
            next[curr]->insert(key + 1);
 
        }
    }
    int find(const char* key){
        int curr = *key - 'a';
        if (*key == '?'){
            int tmp = 0;
            for (int k = 0; k<26; k++){
                if (next[k] != NULL)
                    tmp += next[k]->count;
            }
            return tmp;
        }
        if (next[curr] == NULL) return 0;
        if (*(key + 1) == '?') return next[curr]->count;
        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);
 
 
    for (auto &a : words){
        int size = a.size();
 
        const char *c = a.c_str();
        if (root[size] == NULL) root[size] = new Trie();
        root[size]->insert(c);
 
 
        string reversed_string = a;
        reverse(reversed_string.begin(), reversed_string.end());
 
        const char *k = reversed_string.c_str();
        if (reroot[size] == NULL) reroot[size] = new Trie();
        reroot[size]->insert(k);
 
    }
 
    int idx = 0;
 
    for (auto &a : queries){
 
        int size = a.size();
 
        if (a[size - 1] == '?'){
            const char *c = a.c_str();
 
            if (root[size] == NULL){ idx++; continue; }
            else answer[idx] = root[size]->find(c);
 
        }
        else{
            string re = a;
            reverse(re.begin(), re.end());
            const char *k = re.c_str();
 
            if (reroot[size] == NULL){ idx++; continue; }
            else answer[idx] = reroot[size]->find(k);
        }
        idx++;
    }
 
    return answer;
}