[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;
	}
}