[C++, Trie] 프로그래머스 가사 검색 문제 풀이

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

코딩테스트 연습 - 가사 검색 | 프로그래머스

 

재밌는 문제이다. 이 문제로 인해 트라이 자료구조를 알게 되었다.

트라이는 문자열의 검색에 효율적인 자료구조이며 트리구조로 되어 있다.

처음에 문제를 보면 따로 트라이라는 자료구조를 공부한적 없는 분이라면 대부분 아래와 같은 해답을 떠올릴 것이다.

나 역시 그랬다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include <string> #include <vector>   using namespace std;   vector<int> solution(vector<string> words, vector<string> queries) {     int wsize = words.size();     int qsize = queries.size();       vector<int> answer(qsize, 0);       for (int j = 0; j<qsize; j++){         int qjsize = queries[j].size();         bool front;         int k = 0;         if (queries[j][qjsize - 1] == '?'){             front = false;         }         else {             front = true;             while (queries[j][k] == '?'){                 k++;             }         }         int ktmp = k;         for (int i = 0; i<wsize; i++){             if (words[i].size() != qjsize) continue;               for (k = ktmp; k<words[i].size(); k++){                 if (words[i][k] != queries[j][k] && queries[j][k] != '?')break;                   if (front){                     if (k == words[i].size() - 1)answer[j]++;                 }                 else {                     if (queries[j][k] == '?'){ answer[j]++; break; }                 }             }         }     }       return answer; } Colored by Color Scripter

cs

 

단순히 query 한개에 대해 word를 하나씩 대입하면서 선형으로 검색하여 답을 구하는 코드이다.

이러면 프로그래머스 기준으로 5개의 효율성테스트 중 2개밖에 통과하지 못하게 된다.

그렇다면 카카오에서 올라온 공식자료를 한번 보자.

 

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

해설

- 정확성 풀이 queries에 담긴 문자열을 words에 담긴 문자열과 하나하나 비교하면서 개수를 세면 됩니다.

- 효율성 풀이 queries에 담긴 문자열을 words에 담긴 문자열과 하나하나 비교하는 방법으로는 효율성 풀이를 통과할 수 없습니다. queries에 담긴 문자열이 words에 있는지 탐색하는 효율적인 방법으로 트라이(Trie) 자료구조를 사용할 수 있습니다.이때, 원래 문자열을 이용해 만든 트라이와, 문자열을 뒤집어서 만든 트라이 두 개를 이용해야 합니다. ???가 접두사인 경우는, 문자열을 뒤집어서 ???가 접미사로 나온다고 생각할 수 있기 때문입니다. 예를 들어, “??ost”의 경우 “tso??”로 생각할 수 있습니다.단어를 트라이에 넣을 때는 길이에 따라 서로 다른 트라이에 넣어줘야 합니다. 같은 접두사를 가지더라도 길이에 따라 개수가 달라질 수 있기 때문입니다. 단어 하나의 길이가 최대 1만이기 때문에 길이가 1인 문자열을 넣을 트라이부터 길이가 1만인 문자열을 넣을 트라이까지 생성합니다. 이제 각 단어별로 길이에 맞는 트라이에 넣어줍니다.단어를 넣을 때는 각 문자별로 해당 노드의 count를 1씩 증가시켜 줍니다. 이후에 단어를 검색할 때는 접두사에 해당하는 노드까지 이동한 후 해당 노드의 count를 return 하면 됩니다.이 외에도 문자열을 정렬한 다음 이분탐색하는 방법 등을 사용할 수 있습니다.

 

트라이를 사용하라고 되어 있다. 아래의 블로그에서 개념을 잡고 예시코드를 변형하여 정답을 맞췄다.

https://jason9319.tistory.com/129

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

 

 

//지역변수로 포인터를 초기화해서 오류가 생김
//처음에 물음표가 나올때 예외처리
#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;
}

위의 코드를 작성하며 시간 지체한 실수

1. 처음에 지역변수로 포인터를 생성하였는데 초기화를 안해줘서 오류가 발생하였다.

전역변수로 선언해주던가 항상 초기화를 명심하자.

2. 모두 ? 로 되어있는 쿼리문을 고려해주지 못했다. 모두 ? 로 된 쿼리문을 위해 38-45 줄을 추가하여 

해결할 수 있었다.

 

 

궁금한 점이 있다면 댓글로 부탁드린다.