취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5446번 문제인 용량 부족이다.
문제는 아래 링크를 확인하자.

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

주어진 문자열들의 집합은 trie를 이용해 표현 및 관리할 수 있다.

trie의 각 노드에 해당 노드가 나타내는 문자열을 prefix로 갖는 "지워야하는 문자열"의 개수와 "지우지 말아야 할 문자열의 개수", 그리고 "해당 노드로 끝나는 문자열의 존재여부"의 정보를 기록해두면 trie 위에서의 DFS를 통해 작성해야 할 명령을 합산하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;
typedef unsigned short ushort;

struct node {
	ushort cnt1 = 0, cnt2 = 0;
	ushort child[63] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
	bool chk = 0;
	node() {};
};

node trie[40001];

int N1, N2;

ushort dfs(int id) {
	node& cur = trie[id];

	if (cur.cnt1 == 0) return 0;
	if (cur.cnt2 == 0) return 1;

	ushort ret = 0;
	for (auto& x : cur.child) {
		if (x) ret += dfs(x);
	}

	if (cur.chk) ret++;
	
	return ret;
}

void solve() {
	trie[0] = node();
	cin >> N1;
	ushort trieid = 0;
	while (N1--) {
		string s; cin >> s; ushort cur = 0;
		for (auto& l : s) {
			trie[cur].cnt1++;
			int idx;
			if ('0' <= l && l <= '9') idx = l - '0';
			else if ('a' <= l && l <= 'z') idx = l - 'a' + 10;
			else if ('A' <= l && l <= 'Z') idx = l - 'A' + 36;
			else idx = 62;
			
			ushort& nxt = trie[cur].child[idx];
			if (nxt == 0) {
				nxt = ++trieid;
				trie[nxt] = node();
			}
			cur = nxt;
		}
		trie[cur].cnt1++;
		trie[cur].chk = 1;
	}
	cin >> N2;
	while (N2--) {
		string s; cin >> s; ushort cur = 0;
		for (auto& l : s) {
			trie[cur].cnt2++;
			int idx;
			if ('0' <= l && l <= '9') idx = l - '0';
			else if ('a' <= l && l <= 'z') idx = l - 'a' + 10;
			else if ('A' <= l && l <= 'Z') idx = l - 'A' + 36;
			else idx = 62;

			ushort& nxt = trie[cur].child[idx];
			if (nxt == 0) {
				nxt = ++trieid;
				trie[nxt] = node();
			}
			cur = nxt;
		}
		trie[cur].cnt2++;
	}
	cout << dfs(0) << '\n';
}

int T;

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

	cin >> T;
	while (T--) solve();
}