[BOJ] 용량 부족(5446)

[백준(BOJ)] 용량 부족(5446) C++

문제 : BOJ_5446번 용량 부족

문제 설명

Trie

트라이를 응용해야 풀 수 있는 문제입니다.

지워야 하는 파일과 지우면 안 되는 파일이 모두 주워지는데,

와일드카드 *를 제일 끝에만 사용하여 지울 수 있을 때,

지워야 하는 파일을 모두 지울 수 있는 최소의 횟수를 구해야 합니다.

---

Solution

트라이의 특성상, 문자열의 순서가 자식 트라이 노드로 이어지기 때문에,

bool형 변수를 하나 선언해서 처음에 지워야 하는 파일 이름을 트라이에 하나씩 등록할 때마다

한 글자, 한 글자 bool형을 true로 해줍니다.

그 뒤 지우면 안 되는 파일을 등록할 때, 트라이에 한 글자, 한 글자 모두 bool형을 false로 해줍니다.

트라이를 순회하면서 true인 노드가 보이면 해당 노드와 자식들을 모두 삭제하고 횟수를 카운트해줍니다.

---

Description

지울 수 있는 여부인 bool형을 ok라는 변수로 선언했습니다.

---

#include <iostream>
using namespace std;
int swc,res,tk,n,m;
struct Trie {
    Trie *next[128];
    bool finish;
    bool ok;
    bool first_ok;
    Trie() {
        fill(next, next + 128, nullptr);
        finish = false;
        ok = false;
    }
    ~Trie() {
        for (int i = 0; i < 128; i++) if (next[i]) delete next[i];
    }
    void insert(const char *key) {
        if (*key == '\0') {
            finish = true;
            if (!swc) ok = true;
            else ok = false;
            return;
        }
        if (!swc) {
            ok = true;
        }
        else ok = false;
        int curr = *key;
        if (next[curr] == nullptr) next[curr] = new Trie();
        next[curr]->insert(key + 1);
    }
    void find() {
        if (ok) {
            res++;
            return;
        }
        else if (finish) res++;
        for (int i = 0; i < 128; i++) {
            if (next[i]) next[i]->find();
        }
    }
};
int main(void) {
    scanf("%d", &tk);
    while (tk--) {
        Trie *root = new Trie();
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            char str[21];
            scanf(" %s", str);
            root->insert(str);
        }
        scanf("%d", &m);
        swc = 1;
        for (int i = 0; i < m; i++) {
            char str[21];
            scanf(" %s", str);
            root->insert(str);
        }
        root->find();
        printf("%d\n", res-m);
        res = 0;
        swc = 0;
        delete root;
    }
}