용량 부족

백준 5446번: 용량 부족

아이디어

지워야 하는 파일, 지우면 안 되는 파일 둘 다 트라이에 insert. 이 때 지워야 하는 파일은 노드 마지막에 종료 표시, 지우면 안 되는 파일은 모든 노드에 지울 수 없다고 표시.

노드 하나가 removable 하면 그 모든 자식들도 removable 하다. 바로 지우고 1 return. removable하지 않으면서 지워야 하는 파일의 마지막 노드인 경우 +1.

코드

#include <bits/stdc++.h>

using namespace std;

struct Trie {
    map<char, Trie*> child;
    bool end;
    bool removable;

    Trie() {
        end = false;
        removable = false;
    }

    ~Trie() {
        for (auto ch : child) {
            if (ch.second) delete ch.second;
        }
    }

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

int solve(Trie* node) {
    if (node->removable) return 1;
    int ans = node->end ? 1 : 0;
    for (auto ch : node->child) {
        ans += solve(ch.second);
    }
    return ans;
}

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

    int t;
    cin >> t;
    while (t--) {
        Trie root;
        int n1;
        cin >> n1;
        while (n1--) {
            string s;
            cin >> s;
            root.insert(s, 0, true);
        }
        int n2;
        cin >> n2;
        while (n2--) {
            string s;
            cin >> s;
            root.insert(s, 0, false);
        }
        cout << solve(&root) << '\n';
    }
    
    return 0;
}

여담

문자 종류가 여러가지면 Trie child[N] 하지 말고 map<char, Trie> child 하는게 좋다. 어차피 몇개 안돼서 저게 더 편함.