BOJ5052 전화번호목록

도경원·2023년 3월 20일
0

알고리즘스터디_C++

목록 보기
34/42
#include <iostream>
using namespace std;

struct Trie {
	Trie* node[26];

	Trie() {
		for (int i = 0; i < 26; i++) node[i] = NULL;
	}

	void insert(string& str, int idx) {
		if (idx == str.size())
			return;

		if (node[str[idx] - 'a'] == NULL)
			node[str[idx] - 'a'] = new Trie();

		node[str[idx] - 'a']->insert(str, idx + 1);
	}

	bool find(string& str, int idx) {
		if (idx == str.size())
			return true;

		if (node[str[idx] - 'a'] == NULL)
			return false;

		return node[str[idx] - 'a']->find(str, idx + 1);
	}

	void clear() {
		for (int i = 0; i < 26; i++){
			if (node[i] != NULL) {
				node[i]->clear();
				delete node[i];
			}
		}
	}
};

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

	int n, m;
	cin >> n >> m;

	Trie* root = new Trie();

	for (int i = 0; i < n; i++){
		string str;
		cin >> str;
		root->insert(str, 0);
	}

	int ans = 0;
	for (int i = 0; i < m; i++){
		string str;
		cin >> str;
		if (root->find(str, 0))
			ans++;
	}

	cout << ans << '\n';
	root->clear();
	delete root;
	return 0;
}

트라이의 정석같은 문제
다른 분의 코드를 참고했다

profile
DigitalArtDeveloper

0개의 댓글