[KAKAO BLIND 2020] - 가사 검색

이 문제의 정해는 트라이로 알려져 있는데, 개인적으로는 코테를 준비하기 위해 트라이를 배우는 것은 권장하지 않는다. 카카오 블라인드에서 트라이로 풀 수 있는 두 문제는 모두 트라이가 아닌 다른 방법으로 해결할 수 있고, 코드도 훨씬 짧다.

 

실제로 코딩테스트 과외를 할 때도 절대 이 문제를 트라이로 풀 생각을 하지 말라고 말했고, 아래 풀이는 수업을 하면서 실시간으로 작성한 코드이다.

 

어차피 가능한 경우는 AAA??나 ??AAA 같이, 앞과 뒤에 ?가 붙는 문자들이다.

그런데 생각해보자. AAA??는 AAAAA, AAAAB, .... AAAZY, AAAZZ가 가능할 것이다. 그렇다면 이것은 AAAAA ~ AAAZZ 의 사이에 들어있는 문자를 모두 검색하면 되는 것이고, 다시 말해서 (AAAZZ의 upper_bound) - (AAAAA의 lower_bound)를 구하면 되는 것이다.

 

??AAA 같은 경우는 문자열을 뒤집어버리면 한방에 해결된다.

 

트라이를 안 쓰고 접근하면 생각보다 어렵지 않게 풀 수 있다.

 

#include <bits/stdc++.h>

using namespace std;
vector<string> wrds[10001];
vector<string> wrds_reverse[10001];

vector<int> solution(vector<string> words, vector<string> queries) {
    for(string s : words) {
        wrds[s.size()].push_back(s);
        reverse(s.begin(), s.end());
        wrds_reverse[s.size()].push_back(s);
    }

    for(int i = 1; i < 10001; i++) sort(wrds[i].begin(), wrds[i].end());
    for(int i = 1; i < 10001; i++) sort(wrds_reverse[i].begin(), wrds_reverse[i].end());

    vector<int> answer;

    for(string s: queries) {
        if(s[0] == '?') {
            reverse(s.begin(), s.end());
            string start = s, end = s;
            replace(start.begin(), start.end(), '?', 'a');
            replace(end.begin(), end.end(), '?', 'z');
            answer.push_back(upper_bound(wrds_reverse[s.size()].begin(), wrds_reverse[s.size()].end(), end) - lower_bound(wrds_reverse[s.size()].begin(), wrds_reverse[s.size()].end(), start));
        } else {
            string start = s, end = s;
            replace(start.begin(), start.end(), '?', 'a');
            replace(end.begin(), end.end(), '?', 'z');
            answer.push_back(upper_bound(wrds[s.size()].begin(), wrds[s.size()].end(), end) - lower_bound(wrds[s.size()].begin(), wrds[s.size()].end(), start));
        }
    }

    return answer;
}