[프로그래머스] 가사 검색 (C/C++)

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60060

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

처음에는 정규표현식으로 다음과 같은 코드로 간단하게 풀었었다.

#include <string>
#include <regex>
#include <vector>

using namespace std;

vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    for(auto query : queries) {
        string statement = "";
        
        for(auto character : query) {
            if('a' <= character && character <= 'z') {
                statement += character;
            } else {
                statement += "[a-z]";
            }
        }
        
        regex pattern(statement);
        int count = 0;
        
        for(auto word : words) {
            if(regex_match(word, pattern)) {
                count++;
            }
        }
        
        answer.push_back(count);
    }
    return answer;
}

 

이렇게 풀고나니 정확성은 다 맞았지만 역시 효율성에서 한 케이스도 통과하지 못했다.

그래서 방법을 찾고 있었는데 도저히 생각나지 않아 검색을 해보니 Trie라는 자료구조를 통해 문자열 검색을

O(문자열 길이)에 할 수 있다는 것을 알게 되었고 다음의 블로그를 참고 하여 문제를 풀었다.

 

jason9319.tistory.com/129

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

1. Trie 자료구조를 짜고 word의 길이에 따라 값을 넣어준다.

 

word의 길이에 따라 배열을 선언하여 따로 관리한 이유는 ?를 만나는 즉시 26개의 알파벳 노드를 다 뒤져보고 바로 넘어가기 위함이다. 만약 하나의 루트에서 시작했다면 문자열의 길이를 알 수 없기에 모두 뒤져봐야하기 때문이다.

 

2. 접두사와 접미사에서 부터 ?가 있을 수 있으니 우선 ?의 위치를 찾는다.

 

3. 앞에서부터 시작한다면 query 그대로, 뒤에서부터 시작한다면 reverse하여 찾는 방식으로 시간을 단축하였다.

 

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

const int ALPABET_COUNT = 26;

struct Trie
{
    bool finish;
    int count;
    Trie* next[ALPABET_COUNT];

    Trie() : finish(false), count(1) {
        memset(next, 0, sizeof(next));
    }

    ~Trie()
    {
        for(int index = 0; index <ALPABET_COUNT; index++) {
            if(next[index]) {
                delete next[index];
            }
        }
    }

    void insert(const char* key) {
        if(*key == '\0') {
             finish=true; 
        } else {
            int cur = *key - 'a';

            if(next[cur] == NULL) {
                next[cur] = new Trie();
            } else {
                next[cur] -> count++;
            }

            next[cur] -> insert(key + 1);
        }
    }

    int find(const char* key)
    {
        int cur = *key - 'a';
        if(*key == '?') {
            int temp = 0;

            for(int index = 0; index < ALPABET_COUNT; index++) {
                if(next[index] != NULL) { 
                    temp += next[index] -> count;
                }
            }

            return temp;
        }

        if(next[cur] == NULL) {
            return 0; 
        }

        if(*(key+1) == '?') {
            return next[cur] -> count; 
        }

        return next[cur] -> find(key + 1);
    }
};

Trie* root[10001];
Trie* reverseRoot[10001];

vector<int> solution(vector<string> words, vector<string> queries) {
    int queriesSize=queries.size();
    vector<int> answer(queriesSize, 0);
    
    for(auto word : words) {
        int wordSize = word.size();
        
        const char* wordChar = word.c_str();
        if(root[wordSize] == NULL) {
            root[wordSize] = new Trie(); 
        }

        root[wordSize]->insert(wordChar);
        
        string reverseWord = word;
        reverse(reverseWord.begin(),reverseWord.end());
        
        const char* reverseWordChar = reverseWord.c_str();
        if(reverseRoot[wordSize] == NULL) {
            reverseRoot[wordSize] = new Trie(); 
        }

        reverseRoot[wordSize]->insert(reverseWordChar);
    }
    
    int index = 0;

    for(auto query : queries) {
        int querySize = query.size();

        if(query[querySize-1] == '?') {
            const char* queryChar = query.c_str();

            if(root[querySize]==NULL) {
                index++; 
                continue;
            }

            answer[index] = root[querySize] -> find(queryChar);
        } else {
            string reverseQuery = query;
            reverse(reverseQuery.begin(),reverseQuery.end());

            const char* reverseQueryChar = reverseQuery.c_str();

            if(reverseRoot[querySize] == NULL) {
                index++; 
                continue; 
            }

            answer[index] = reverseRoot[querySize] -> find(reverseQueryChar);
        }

        index++;
    }

    return answer;
}