문제 링크: 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를 쓰니까 맵 개수가 엄청 늘어나서 그런거같은데... 동적할당 안하고 짜는 좋은 방법이 없을지.. 흐음.... 생각좀 해봐야겠습니다.
반응형
'Online Judge > 백준' 카테고리의 다른 글
[백준][C++] 1051: 숫자 정사각형 (0) | 2020.07.17 |
---|---|
[백준][C++] 17390: 이건 꼭 풀어야 해! (0) | 2020.07.17 |
[백준][C++] 14725: 개미굴 (0) | 2020.07.16 |
[백준][C++] 5052: 전화번호 목록 (0) | 2020.07.16 |
[백준][C++] 14582: 오늘도 졌다 (0) | 2020.07.16 |