[BOJ] 5446 용량 부족

문제: https://www.acmicpc.net/problem/5446

 

문제 풀이:

1. 지워야 할 파일들을 trie에 insert 

2. 지우면 안 될 파일들이 이름이 trie에 존재하는 것들과 겹치는 부분을 체크 (no=true)

3. 전체 trie 순환하면서 no가 아닌 부분에 도달하면 res++하고 그 라인은 더 이상 보지 않음

 

* [rm *]이 가능하려면 root에 존재하는 모든 next에 대해 no 플래그가 off 되어 있어야 한다.

이를 체크하기 위해 2번 작업을 수행하다 no를 한 번이라도 체크하게 되면 root->no=true가 되게 하였다.

root->no가 false라면 rm *이 가능하므로 답은 1이 된다.

 

소스코드:

#include <iostream>
#define QSIZE 63002
using namespace std;

int res;
struct trie {
	trie* next[63];
	bool finish;
	bool no;

	trie() {
		for (int i = 0; i < 63; i++) {
			next[i] = nullptr;
		}
		finish = false;
		no = false;
	}
	~trie() {
		for (int i = 0; i < 63; i++) {
			if(!next[i]) delete next[i];
		}
	}
	void insert(const char * key) {
		if (*key == '\0') {
			finish = true;
			return;
		}
		int n=62;
		if ('a' <= *key&&*key <= 'z') n = *key - 'a';
		else if ('A' <= *key&&*key <= 'Z') n = (*key - 'A') + 26;
		else if ('0'<=*key &&*key<='9') n = (*key-'0')+52;
		if (!next[n]) {
			next[n] = new trie();
		}
		next[n]->insert(key + 1);
	}
	void check(const char * key) {
		if (*key == '\0') return;
		
		int n = 62;
		if ('a' <= *key&&*key <= 'z') n = *key - 'a';
		else if ('A' <= *key&&*key <= 'Z') n = (*key - 'A') + 26;
		else if ('0' <= *key &&*key <= '9') n = (*key - '0') + 52;
		
		if (next[n]) {
			next[n]->no = true;
			no = true;
		}
		else return;
		next[n]->check(key + 1);
	}
};
trie *qq[QSIZE];

int tc, n, m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		res = 0;
		trie *root = new trie;
		cin >> n;
		for (int i = 0; i < n; i++) {
			char c[22];
			cin >> c;
			root->insert(c);
		}
		
		cin >> m;
		for (int j = 0; j < m; j++) {
			char c[22];
			cin >> c;
			root->check(c);
		}

		if (!root->no) {
			cout << "1\n";
			continue;
		}
		qq[0] = root;
		int front = 0;
		int top = 1;
		while (front != top) {
			trie* cur = qq[front];
			front = (front + 1) % QSIZE;
			for (int i = 0; i < 63; i++) {
				if (cur->next[i]) {
					if (cur->next[i]->no) {
						if (cur->next[i]->finish) res++;
						qq[top] = cur->next[i];
						top = (top + 1) % QSIZE;
					}
					else res++;
				}
			}
		}
		cout << res << '\n';
	}

	return 0;
}