[백준/BOJ] 백준 5446번 : 용량 부족

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

5446번: 용량 부족

 

트라이를 이용하여 삭제할 문자열과, 남길 문자열을 저장했으며 트라이의 각 노드에서 자식 노드에 대한 삭제할 문자열과 남길 문자열의 정보를 저장하여, 특정 노드에서 와일드카드를 달아서 지울 수 있는지, 또는 해당 노드에서 삭제할 문자열이 끝나서 지워야 하는지를 판단하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int tc;
int n1, n2;

struct node {
	bool remove_finish;
	bool remain_finish;
	int remove_child_cnt;
	int remain_child_cnt;
	node* children[63]; //소문자(26), 대문자(26), 숫자(10), 점(1)
	int remove_child_check[63];
};

node* NewNode() {
	node* ret = new node();
	ret->remove_finish = false;
	ret->remain_finish = false;
	ret->remove_child_cnt = 0;
	ret->remain_child_cnt = 0;
	for (int i = 0; i < 63; i++) {
		ret->children[i] = NULL;
		ret->remove_child_check[i] = 0;
	}

	return ret;
}

void DeleteNode(node*& here) {

	if (here == NULL) {
		return;
	}

	for (int i = 0; i < 63; i++) {
		DeleteNode(here->children[i]);
	}

	delete here;
}

void InsertRemove(node*& here, string& input, int index) {

	if (input.size() == index) {
		here->remove_finish = true;
		return;
	}

	here->remove_child_cnt++;

	if (input[index] >= 'a' && input[index] <= 'z') { //소문자일때
		if (here->children[input[index] - 'a'] == NULL) {
			here->children[input[index] - 'a'] = NewNode();
			here->remove_child_check[input[index] - 'a']++;
			InsertRemove(here->children[input[index] - 'a'], input, index + 1);
		}

		else {
			here->remove_child_check[input[index] - 'a']++;
			InsertRemove(here->children[input[index] - 'a'], input, index + 1);
		}
	}

	else if (input[index] >= 'A' && input[index] <= 'Z') { //대문자일때
		if (here->children[input[index] - 'A' + 26] == NULL) {
			here->children[input[index] - 'A' + 26] = NewNode();
			here->remove_child_check[input[index] - 'A' + 26]++;
			InsertRemove(here->children[input[index] - 'A' + 26], input, index + 1);
		}

		else {
			here->remove_child_check[input[index] - 'A' + 26]++;
			InsertRemove(here->children[input[index] - 'A' + 26], input, index + 1);
		}
	}

	else if (input[index] >= '0' && input[index] <= '9') { //숫자일때
		if (here->children[input[index] - '0' + 52] == NULL) {
			here->children[input[index] - '0' + 52] = NewNode();
			here->remove_child_check[input[index] - '0' + 52]++;
			InsertRemove(here->children[input[index] - '0' + 52], input, index + 1);
		}

		else {
			here->remove_child_check[input[index] - '0' + 52]++;
			InsertRemove(here->children[input[index] - '0' + 52], input, index + 1);
		}
	}

	else { //점일때
		if (here->children[62] == NULL) {
			here->children[62] = NewNode();
			here->remove_child_check[62]++;
			InsertRemove(here->children[62], input, index + 1);
		}

		else {
			here->remove_child_check[62]++;
			InsertRemove(here->children[62], input, index + 1);
		}
	}

}

void InsertRemain(node*& here, string& input, int index) {

	if (input.size() == index) {
		here->remain_finish = true;
		return;
	}

	here->remain_child_cnt++;

	if (input[index] >= 'a' && input[index] <= 'z') { //소문자일때
		if (here->children[input[index] - 'a'] == NULL) {
			here->children[input[index] - 'a'] = NewNode();
			InsertRemain(here->children[input[index] - 'a'], input, index + 1);
		}

		else {
			InsertRemain(here->children[input[index] - 'a'], input, index + 1);
		}
	}

	else if (input[index] >= 'A' && input[index] <= 'Z') { //대문자일때
		if (here->children[input[index] - 'A' + 26] == NULL) {
			here->children[input[index] - 'A' + 26] = NewNode();
			InsertRemain(here->children[input[index] - 'A' + 26], input, index + 1);
		}

		else {
			InsertRemain(here->children[input[index] - 'A' + 26], input, index + 1);
		}
	}

	else if (input[index] >= '0' && input[index] <= '9') { //숫자일때
		if (here->children[input[index] - '0' + 52] == NULL) {
			here->children[input[index] - '0' + 52] = NewNode();
			InsertRemain(here->children[input[index] - '0' + 52], input, index + 1);
		}

		else {
			InsertRemain(here->children[input[index] - '0' + 52], input, index + 1);
		}
	}

	else { //점일때
		if (here->children[62] == NULL) {
			here->children[62] = NewNode();
			InsertRemain(here->children[62], input, index + 1);
		}

		else {
			InsertRemain(here->children[62], input, index + 1);
		}
	}
}

int Solve(node*& here) {

	//현재 위치와 아래에서 남겨야 하는 파일이 없을때
	//여기서 와일드카드를 달아서 다 지운다
	if (here->remain_child_cnt == 0 && here->remain_finish == false) {
		return 1;
	}

	//현재 위치 또는 아래에 남겨야 하는 파일이 있을때

	int ret = 0;

	//여기서 끝나는 지워야 하는 파일이 있을때
	if (here->remove_finish == true) {
		ret++;
	}

	for (int i = 0; i < 63; i++) {

		//해당 방향에 지워야할 파일이 있을때
		if (here->children[i] != NULL && here->remove_child_check[i] != 0) {
			ret += Solve(here->children[i]);
		}
	}

	return ret;
}

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

	cin >> tc;

	for (int t = 0; t < tc; t++) {

		node* root = NewNode();

		cin >> n1;
		for (int i = 0; i < n1; i++) {
			string input;
			cin >> input;

			InsertRemove(root, input, 0);
		}

		cin >> n2;
		for (int i = 0; i < n2; i++) {
			string input;
			cin >> input;

			InsertRemain(root, input, 0);
		}

		cout << Solve(root) << "\n";

		DeleteNode(root);
	}

	return 0;
}