백준[5446] 용량 부족

문제 설명

문제 설명

http://icpc.me/5446

5446번: 용량 부족

풀이

트라이를 이용해서 풀 수 있다.

트라이에 문자열을 삽입할 때, 지워야 하는 문자열이 끝날 때, 지워야 하는 문자인지, 지우면 안 되는 문자인지를 체크하며 삽입을 한다.

그럼 어떠한 한 노드의 상황 3가지이다.

1. 지워야 하고, 지워도 되는 상황 -> 자식 노드까지 한 번에 지워버린다

2. 지우면 안 되면서, 어떤 지워야 하는 문자열의 마지막 문자인 상황 -> *없이 rm abc와 같이 지운다

3. 지워야 하지만 지우면 안 되는 상황 -> 자식 노드로 이동하여 rm ~~*로 지울 수 있는지 확인

cf) N2가 0이면 지우면 안 되는 파일이 없기 때문에 rm *로 모두 지워도 된다.

코드

#include <cstdio>
#include <cstring>
#include <unordered_map>

using namespace std;

struct Trie {
    unordered_map<char, Trie*> nxt;
    bool dontDel;
    bool doDel;
    bool doDelEnd;
    Trie() : dontDel(false), doDel(false), doDelEnd(false) { }
    ~Trie() {  for (auto &[c, trie] : nxt) delete trie; }
    
    void insert(const char *s, bool flag) {
        if (*s == 0) return;
        if (!nxt.count(*s)) nxt[*s] = new Trie();
        
        if (flag) nxt[*s] -> dontDel = true;
        else nxt[*s] -> doDel = true;

        if (!flag && *(s + 1) == 0) {
            nxt[*s] -> doDelEnd = true;
            return;
        }
        nxt[*s] -> insert(s + 1, flag);
    }

    int find() {
        bool flag = true;
        int ret = 0;
        for (auto &[c, trie]: nxt) if (trie -> doDel) {
        	// 1번 상황
            if (!(trie -> dontDel)) ret++;
            // 2번 상황
            if (trie -> doDelEnd && trie -> dontDel) ret++;
            // 3번 상황
            if (trie -> dontDel) ret += trie -> find();
        }        
        return ret;
    }
};

void solve() {
    Trie *root = new Trie();
    int n1; scanf("%d", &n1);
    for (int i = 0; i < n1; i++) {
        char s[22]; scanf("%s", s);
        root -> insert(s, false);
    }
    int n2; scanf("%d", &n2);
    for (int i = 0; i < n2; i++) {
        char s[22]; scanf("%s", s);
        root -> insert(s, true);
    }
    printf("%d\n", n2 ? root -> find() : 1);
    delete root;
}

int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
}