[BOJ] 14425 문자열 집합 - trie / map으로 풀기

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

 

 

문제 설명:

1. n과 m을 입력 받음

2. n개의 문자열을 입력 받음(형광펜) -> 집합 S

3. m개의 문자열을 입력 받음 

   이 때 입력 받은 문자열이 집합 S에 있으면 cnt++

 

* baekjoon은 집합 S에 포함되는거 아님

  baekjoononlinejudge처럼 완전히 일치하는 것만 포함되는 걸로 취급

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 풀이:

Trie

메모리 제한이 1536 MB로 넉넉하므로 trie로 풀어보았다.

insert함수로 trie를 만들고

check함수로 포함되는지 확인 했다.

 

check함수에서

현재 문자열이 새로운 길로 가려고 하면 S에 포함되지 않는 것이므로 ->  false 리턴

현재 문자열을 끝까지 다 봤고 S에 속하는 문자열도 이 곳에서 끝났으면 같은 문자열임 -> true 리턴

 

Map:

그냥 S 맵에 각각 넣고 m개 입력 받을 때, S에 있으면 cnt++

 

 

 

소스 코드:

 

Trie 코드:

#include <iostream>
using namespace std;

int n, m,cnt;

struct trie {
	trie* next[26];
	bool finish;

	trie() {
		fill(next, next + 26, nullptr);
		finish = false;
	}
	~trie() {
		for (int i = 0; i < 26; i++) {
			if (next[i]) delete(next[i]);
		}
	}
	void insert(const char *key) {
		if (*key == '\0') {
			finish = true;
			return;
		}
		int num = *key - 'a';
		if (!next[num]) next[num] = new trie();
		
		next[num]->insert(key + 1);

		return;
	}
	bool check(const char *key) {
		if (*key == '\0') {
			return finish;
		}
		int num = *key - 'a';
		if (!next[num]) return false;
		bool get = next[num]->check(key + 1);

		return get;
	}
};

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

	cin >> n >> m;
	trie *t = new trie();

	for (int i = 0; i < n; i++) {
		char ch[500];
		cin >> ch;
		t->insert(ch);
	}
	for (int i = 0; i < m; i++) {
		char ch[500];
		cin >> ch;
		if (t->check(ch)) cnt++;
	}
	cout << cnt << '\n';
	return 0;
}

 

map 코드:

#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>
using namespace std;

int n, m,cnt;
string s;
unordered_map<string, bool> ma;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s;
		ma[s] = true;
	}
	for (int i = 0; i < m; i++) {
		cin >> s;
		if (ma[s]) cnt++;
	}
	cout << cnt << '\n';
}