문제 링크: https://www.acmicpc.net/problem/14425

 

푸는 방법은 여러가지입니다. 이분탐색 해도 되고 트라이 만들어도 되고..

근데 가장 간단한건 그냥 해쉬테이블 만드는겁니다. std::unordered_set 쓰면 간단합니다

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	unordered_set<string> us;
	int n, m;
	cin >> n >> m;

	while (n--) {
		string s;
		cin >> s;
		us.insert(s);
	}

	int cnt = 0;
	while (m--) {
		string s;
		cin >> s;
		if (us.find(s) != us.end())
			++cnt;
	}
	cout << cnt << '\n';

	return 0;
}

해쉬 쓴 버전입니다.

 

#include <bits/stdc++.h>
using namespace std;

struct trie_node {
	map<char, trie_node> children;
	bool terminal;

	trie_node() : terminal(false) {}
};

void trie_insert(trie_node& root, const string& s) {
	trie_node* curr = &root;
	for (const auto& c: s) {
		if (curr->children.find(c) == curr->children.end())
			curr->children[c] = trie_node();

		curr = &(curr->children[c]);
	}

	curr->terminal = true;
}

bool trie_search(const trie_node& root, const string& s) {
	const trie_node* curr = &root;
	for (const auto& c : s) {
		if (curr->children.find(c) == curr->children.end())
			return false;

		curr = &(curr->children.at(c));
	}

	return curr->terminal;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	trie_node root;

	int n, m;
	cin >> n >> m;
	
	while (n--) {
		string s;
		cin >> s;
		trie_insert(root, s);
	}

	int counter = 0;
	while (m--) {
		string s;
		cin >> s;
		counter += trie_search(root, s);
	}
	cout << counter << '\n';

	return 0;
}

노드가 map<char, node>인 트라이로 구현한 버전입니다. solved.ac 태그에 있길래 트라이로 풀어봤는데.. 굳이...

메모리를 546mb 정도 쓰고, 시간은 900ms가 걸리네요.

흐음.... key로 char를 쓰니까 맵 개수가 엄청 늘어나서 그런거같은데... 동적할당 안하고 짜는 좋은 방법이 없을지.. 흐음.... 생각좀 해봐야겠습니다.

반응형