백준 19585번 전설

백준 19585번: 전설

아이디어

색상은 trie에 insert, 닉네임은 unordered_set에 insert. 그리고 쿼리 앞부분부터 트라이에서 찾는다. 트라이에 알파벳이 존재하지 않으면 return false, 트라이에 해당 색상이 존재하고, 뒷쪽 substring이 unordered_set에 존재하면 return true, 끝까지 다 돌았는데도 못찾으면 return false.

코드

#include <bits/stdc++.h>

using namespace std;

unordered_set<string> team;

struct Trie {
    Trie* t[26];
    bool end;

    Trie() {
        memset(t, 0, sizeof(t));
        end = false;
    }

    ~Trie() {
        for (int i = 0; i < 26; i++) {
            if (t[i]) delete t[i];
        }
    }

    void insert(string& s, int idx) {
        if (idx == s.length()) {
            end = true;
            return;
        }
        if (!t[s[idx]-'a']) {
            t[s[idx]-'a'] = new Trie();
        }
        t[s[idx]-'a']->insert(s, idx+1);
    }

    bool solve(string& s, int idx) {
        if (idx == s.length()) return false;
        if (!t[s[idx]-'a']) return false;
        if (t[s[idx]-'a']->end && team.find(s.substr(idx+1)) != team.end()) return true;
        return t[s[idx]-'a']->solve(s, idx+1);
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    Trie root;
    int c, n, q;
    cin >> c >> n;
    while (c--) {
        string s;
        cin >> s;
        root.insert(s, 0);
    }
    while (n--) {
        string s;
        cin >> s;
        team.insert(s);
    }
    cin >> q;
    while (q--) {
        string s;
        cin >> s;
        if (root.solve(s, 0)) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

여담

정답률 단 14% 1트 성공..!