카카오 2020 4번 - 가사 검색(트라이)

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

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

 

트라이로 푼 문제

 

find를 비재귀로 했다가 효율성 3번만 계속 틀렸다

 

진짜 미쳐버리는줄 알았다 시간도 더빠르고 메모리도 동일한데 뭐가 문제란 말인지

 

정확성 테스트에서 예외 확인하고 효율성에서 시간 확인하는게 아닌건가??

 

맞왜틀

 

진자로 너무 화가낫다..

 

발상 자체는 금방 했는데 저 3번때문에 며칠을 꼬라박았다

 

답은 재귀였다.

 

아나

 

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
struct Trie
{
    Trie()
    {
        memset(next, 0, sizeof(next));
        /*for (int i = 0; i < 26; ++i)
        {
            next[i] = nullptr;
        }*/
    }
    ~Trie()
    {
        for (int i = 0; i < 26; ++i)
        {
            if (next[i])
            {
                //std::cout << (char)('a' + i);
                delete next[i];
                //std::cout << '\n';
            }
        }
    }
 
    void insert(const char* word)
    {
        if (*word == '\0')
        {
            return;
        }
        ++size;
 
        int idx = *word - 'a';
        if (next[idx] == nullptr)
        {
            next[idx] = new Trie;
        }
        next[idx]->insert(word + 1);
    }
 
    unsigned int find_how_many(const char* word)
    {
        //엉뚱한 글자가 나오면 0을 리턴합니다
        if (next[word[0] - 'a'] == nullptr)
        {
            return 0;
        }
        // "?????"같은 상황을 대비해 첫글자가 '\0'이라면 해당 글자수의 모든 사이즈를 리턴합니다
        //if (*word == '\0')
        if (*word == '?')
        {
            return size;
        }
        
        //word를 따라가기 위한 idx 변수를 만듭니다.
        unsigned int idx = 0;
        //트라이의 링크를 따라가기 위한 tour변수를 만들었습니다.
        Trie* tour = next[word[idx++] - 'a'];
        //'f????'같은 상황을 대비해 idx를 올리고 검사합니다.
        //if (word[idx] == '\0')
        if (word[idx] == '?')
        {
            return tour->size;
        }
 
        //word와 트라이 링크를 같이 따라갑니다
        while (tour->next[word[idx] - 'a'] != nullptr)
        {
            tour = tour->next[word[idx++] - 'a'];
 
            //if (word[idx] == '\0')
            if (word[idx] == '?')
            {
                //word의 끝이 나오면 사이즈를 리턴합니다
                return tour->size;
            }
        } 
        return 0;
    }
 
    //unsigned int find_how_many(const char* word)
    //{
    //    if (*word == '?')
    //    {
    //        return size;
    //    }
    //    if (next[word[0] - 'a'] == nullptr)
    //    {
    //        return 0;
    //    }
 
    //    return next[word[0] - 'a']->find_how_many(word + 1);
    //}
 
public:
    Trie* next[26];
    unsigned int size = 0;
};
 
Trie trieArr[10001];
Trie rtrieArr[10001];
 
vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer(queries.size());
    //std::unordered_map<int, Trie> trieArr;
    //std::unordered_map<int, Trie> rtrieArr;
    //trieArr.reserve(10010);
    //rtrieArr.reserve(10010);
 
    std::string token;
    for (auto& it : words)
    {
        //입력받은 단어를 정방향으로 한번, 역방향으로 한번 넣었습니다.
        token.clear();
        token = it;
        std::reverse(token.begin(), token.end());
        rtrieArr[it.size()].insert(token.c_str());
        trieArr[it.size()].insert(it.c_str());
    }
 
    int idx = 0;
    for (auto& it : queries)
    {
        //첫글자가 ?이 아니면 정방향, ?이 나올때까지 쿼리의 단어를 token에 넣고 find를 돌렸습니다
        token.clear();
        if (it.front() != '?')
        {
 
            //int i = 0;
            //while (it[i] != '?')
            //{
            //    token += it[i++];
            //}
            //token += '\0';
            
            //answer[idx++] = trieArr[it.size()].find_how_many(token.c_str());
            
            answer[idx++] = trieArr[it.size()].find_how_many(it.c_str());
        }
        else
        {
            //첫글자가 ?이면 역방향, 위와 마찬가지로 ?가 나올때까지 역방향으로 token에 넣고 find 함수에 넣었습니다
            
            std::reverse(it.begin(), it.end());
            //int i = it.size() - 1;
            //while (it[i] != '?')
            //{
            //    token += it[i--];
            //}
            //token += '\0';
 
            //answer[idx++] = rtrieArr[it.size()].find_how_many(token.c_str());
            
            answer[idx++] = rtrieArr[it.size()].find_how_many(it.c_str());
        }
    }
    return answer;
}
 
int main()
{
    std::vector<std::string> words = { "frodo", "front", "frost", "frozen", "frame", "kakao" };
    std::vector<std::string> queries = { "fro??", "????t", "fr???", "fro???", "pro?" };
    for (auto it : solution(words, queries))
    {
        std::cout << it << ' ';
    }
    return 0;
}

문제의 틀린 답. 주석처리 된 find_how_many 재귀함수를 사용하면 정답이다.