[백준] BOJ 19585 : 전설

https://www.acmicpc.net/problem/19585

19585번: 전설

문제의 조건들을 파악해봅시다.

 

1. 색상들의 이름들과, 닉네임들이 C, N개씩 주어짐

2. 이후에 Q개의 팀 이름들이 주어질 때, 각 이름들이 <색상들의 이름>이 나온다음에 <닉네임>이 나오는 구조로 이루어져 있는가를 출력

 

조건만 보면 일단 단순합니다. 문제 길이도 그렇게 길지는 않죠.

 

다만, 색상의 종류와 닉네임의 개수가 C, N개인데 모든 조합을 파악하기에는 4000 * 4000 개이며, concatenate 비용도 O(N)이므로 색상과 닉네임의 최대 길이 1000을 N으로 잡으면 4000 * 4000 * 2000 정도가 됩니다. 그것 뿐만이 아니라 각 팀 이름들이 이 조합 안에 들어가는가도 파악하는 것도 비용이 꽤 클 것입니다. 좀 더 똑똑하게 이를 풀어야 합니다.

 

여러 구현 방법이 있을 것 같지만, 일단 여러 문자열이 주어지고 이를 관리하는 데이터구조인 Trie가 저는 먼저 떠올랐습니다. Trie를 활용한다면 O(N)만에 "여러 문자열 중에서 특정 문자열에서 Prefix / Suffix로 존재하는 문자열이 존재하는가?"를 해결할 수 있습니다. 그래서 저는 색깔 및 닉네임들을 따로 관리하는 Trie 두 개를 생성해두었습니다. 편의상 색깔은 원래 방향대로 저장을 하였고, 닉네임은 역순으로 저장하였습니다. (예시 : joker 라는 닉네임은 r - e - k - o - j  이 순서대로 저장해두었습니다.)

 

다만, 고려해야 할 점이 하나 더 있습니다. 아래와 같은 예제를 생각해봅시다.

2 1
red
redre
redcan
1
redredcan

일단 이 예제의 정답은 "YES"가 출력이 되어야 합니다. red / redcan 이렇게 나눌 수 있으니깐 말이죠. 다만, 그냥 무작정 색깔을 저장하는 Trie에서 검색을 할 때, 가능한 최대한 길게 검색하도록 구현한다면 redre 까지 찾을 겁니다. 그렇다면 뒤에 있는 dcan 은 닉네임에 존재하지 않으므로 "NO"를 출력하겠죠.

 

이를 해결하기 위해서 저는 먼저 끝이날 수 있는 부분들도 노드들에 전부 기록해두도록 구현했습니다. 그래서 실제로 끝이날 수 있는 경우에는 어디 index까지 찾았는지를 저장하도록 했습니다. 이후 닉네임들을 검색할 때에 가능한 닉네임이라면 전에 색깔을 찾은 index도 여기서 끝이 나는지를 찾아보아 가능하다면 "YES"를 출력 아니면 "NO"를 출력하도록 구현했습니다. (Meet In The Middle과 유사한 아이디어라고 생각합니다.)

 

제가 구현한 코드는 아래와 같습니다.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
// Default

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// PBDS

struct Node{
    bool end; // 끝나는 가?
    map<int, Node *> low; // Child Node 관리 -> Map을 활용하면 속도는 떨어집니다만 메모리를 아낄 수 있습니다.
    Node (){
        end = false;
    }
}; // Trie Node 구현

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll N, M;
    cin >> N >> M;

    Node * head1 = new Node(); // 색깔 관리용 Trie
    Node * head2 = new Node(); // 닉네임 관리용 Trie

    for(int i =0; i<N; ++i){
        string s;
        cin >> s;
        Node * curr = head1;
        for(int j =0; j<s.size(); ++j){
            int idx = s[j]-'a';
            if(curr->low.find(idx) == curr->low.end()) curr->low[idx] = new Node();
            curr = curr->low[idx];
        } // 원래 순서대로
        curr->end = true;        
    } // 색깔 저장
    for(int i =0; i<M; ++i){
        string s;
        cin >> s;
        Node * curr = head2;
        for(int j =s.size()-1; j>-1; --j){
            int idx = s[j]-'a';
            if(curr->low.find(idx) == curr->low.end()) curr->low[idx] = new Node();
            curr = curr->low[idx];
        } // 역순으로
        curr->end = true;        
    } // 닉네임 저장

    ll Q;
    cin >> Q;
    for(int i =0; i<Q; ++i){
        string q;
        cin >> q;

        bool flag = false;
        Node * curr = head1;
        int j = 0;
        int sz = q.size();
        vector<ll> v;
        while(true){
            if(curr->end){ // 색깔로 볼 수 있다면
                v.push_back(j); // index를 저장
            } 
            if(j == sz) break;
            int idx = q[j] - 'a';
            if(curr->low.find(idx) == curr->low.end()) break; // 더 이상 Prefix로 존재하는 색깔이 없다면 종료
            curr = curr->low[idx];
            ++j;
        } // 해당 문자열의 Prefix 중에서 색깔로 존재하는게 어디어디 있는가를 탐색

        curr = head2;
        j = sz-1;
        while(true){
            if(curr->end){ // 닉네임으로 볼 수 있다면
                auto itr = lower_bound(v.begin(), v.end(), j+1);
                if(itr == v.end());
                else if(*itr == j+1){
                    flag = true;
                    break;
                } // 이분탐색을 통해서 앞의 Prefix도 색깔인지를 확인 (MITM 응용)
            }
            if(j == -1) break;

            int idx = q[j] - 'a';
            if(curr->low.find(idx) == curr->low.end()) break; // 더 이상 Suffix로 존재하는 닉네임이 없다면 종료
            curr = curr->low[idx];
            --j;
        } // 역순으로 보면서 해당 문자열의 Suffix 중에서 닉네임으로 존재하는게 어디어디 있는가를 탐색
        //  for(int i : v){
        //      cout << i<<" ";
        // }
        
        if(flag) cout <<"Yes\n";
        else cout <<"No\n";
    }
    
    return 0;
} // Trie
// O((Q+N+M)|S|)

Trie는 알아두면 유용한 자료구조입니다. 특히나 XOR 문제 같은 경우에는 Trie를 활용하는 경우도 존재합니다.(놀랍게도 XOR 최댓값 / 최솟값 구하기 등등이 가능합니다!) 다음에 기회가 된다면 Trie를 활용하는 문제를 들고 올 수 있으면 좋겠네요. 제 2회 보라매컵 이후에 오랜만에 본 Trie 문제였습니다.