프로그래머스 가사 검색(2020 KAKAO BLIND RECRUITMENT)

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

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

 

문제접근법 : 단순히 Trie를 이용하여 풀었을땐 효율성에서 3개정도가 시간초과가 나오더군여

아무리생각해도 잘 접근할수가없어 여러가지를 참고했는데

문제를 좀더 정확히 읽었어야했습니다.

queries의 문자열이 ?가 반드시 존재하지만 접두사혹은 접미사에 해당한다는것을 몰랐었네요

즉 ?를 만날때 그 해당 문자열의 사이즈만 가지고도 해당 나머지 사이즈가 몇개의 문자열들이 있는지만 확인하면 전부 매칭할수있어 trie의 원래문자열과 완전히 거꾸로만든 반대문자열을 만들고

?가 접두사에 있다면 queries를 거꾸로한다음 trie의 반대문자열들을 찾고

?가 접미사에 있따면 원래의 trie의문자열에서 찾는다면 해결할수 있습니다.

 

소스코드 : 

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 44 45 46

//By 콩순이냉장고 #include <bits/stdc++.h> using namespace std; struct Trie {     bool terminal = false;     unordered_map<char, Trie*> children;     unordered_map<int, int> m;     void insert(string& s, int idx = 0) {         m[s.size() - idx]++;         if (s[idx] == 0) {             terminal = true;             return;         }         char next = s[idx];         if (children[next] == NULL)              children[next] = new Trie();         children[next]->insert(s, idx + 1);     }     int find(string& s, int idx = 0) {         char next = s[idx];         if (next == '?') return m[s.size() - idx];         else if(children.count(next)){             return children[next]->find(s, idx + 1);         }         return 0;     } }; vector<int> solution(vector<string> words, vector<string> queries) {     vector<int> answer;     Trie trie,rtrie;     for (string& s : words) {         string rs(s.rbegin(), s.rend());         trie.insert(s);         rtrie.insert(rs);     }     for (string& s : queries) {         if (s[0] == '?') {             reverse(s.begin(), s.end());             answer.push_back(rtrie.find(s));         }         else {             answer.push_back(trie.find(s));         }     }     return answer; } Colored by Color Scripter

cs

 

 

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.