[백준] 14425번 문자열 집합 (트라이)

링크

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

14425번: 문자열 집합

풀이

 

M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 문제이다.

 

간단하게 집합 S를 map에 추가 하고나서

M개의 문자열을 map과 매핑하여 포함 여부를 확인하면 된다.

 

1. map 이용

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 30
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

set<string> _set;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M; cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string word; cin >> word;
		_set.insert(word);
	}

	int cnt = 0;
	for (int i = 0; i < M; i++) {
		string word; cin >> word;
		if (_set.find(word) != _set.end())
			cnt++;
	}
	
	cout << cnt;

}

 

또 다른 방법으로는 trie를 이용하여 풀었습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 30
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

struct Trie {
	Trie *node[SIZE];
	bool is_finish, is_child;

	Trie() {
		fill(node, node + SIZE, nullptr);
		is_finish = is_child = false;
	}

	~Trie() {
		for (int i = 0; i < SIZE; i++) {
			if (node[i])
				delete node[i];
		}
	}

	void insert(string &word, int word_size, int index) {
		if (index >= word_size) {
			is_finish = true;
			return;
		}

		int word_index = word.at(index) - 'a';
		if (node[word_index] == NULL) {
			node[word_index] = new Trie();
			is_child = true;
		}
		node[word_index]->insert(word, word_size, index + 1);
	}

	bool find(string &word, int word_size, int index) {
		bool res = false;
		if (index >= word_size) {
			if (is_finish)
				return true;
			else
				return false;
		}
		else if (index < word_size) {
			int word_index = word.at(index) - 'a';
			if (node[word_index] == NULL || is_finish == true || is_child == false) {
				return false;
			}

			res = node[word_index]->find(word, word_size, index + 1);
		}

		return res;
	}
};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	Trie root;
	int N, M; cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string word; cin >> word;
		root.insert(word, word.size(), 0);
	}

	int cnt = 0;
	for (int i = 0; i < M; i++) {
		string word; cin >> word;
		if (root.find(word, word.size(), 0)) {
			cnt++;
		}
	}

	cout << cnt;

}

 

그 결과

 

위의 결과가 trie를 이용하여 푼 결과이고

밑의 결과가 map를 이용하여 푼 결과이다.

 

일단 map으로 푼 문제의 시간복잡도는 o(문자열의 갯수(10000)*map의 탐색 시간(log10000)) 이고

trie를 이용한 문제의 시간복잡도는 o(문자열의 갯수(10000)* trie의 탐색 시간 즉 문자열의 길이(500)) 이므로

 

trie을 이용한것이 map을 이용한것보다 시간이 올래 걸리는것을 알 수 있습니다.