문제 링크: https://www.acmicpc.net/problem/14725
음... 어떻게 풀까 고민을 좀 했는데요, 간단하게 트라이의 노드를 map<string, 인덱스>
로 만들면 됩니다. N, K 조건이 빡빡하지 않기 때문에 적당히 풀면 됩니다
여기서 map의 value를 인덱스를 쓸지, 포인터를 쓸지는 뭐 구현하는 사람 마음입니다. 저는 요즘 트라이를 배열로 짜는 연습중이라 배열로 만들었습니다.
출력은 preorder로 짜면 됩니다. root는 빼고 나머지만 출력하면 됩니다.
std::map
은 기본적으로 비내림차순으로 정렬된 상태고, iterator를 써서 순회하면 비내림차순으로 순회하게 됩니다.
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
map<string, int> trie[15001]; // name, next_idx
int trie_size;
void trie_insert(const vector<string>& vs) {
int node = 0;
for (auto& s : vs) {
if (trie[node].find(s) == trie[node].end()) {
trie[node][s] = ++trie_size;
node = trie_size;
}
else
node = trie[node][s];
}
}
void print_trie(int node, int depth) {
for (auto& [s, i] : trie[node]) {
cout << string(depth * 2, '-') << s << '\n';
print_trie(i, depth+1);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n;
cin >> n;
while (n--) {
int k;
cin >> k;
vector<string> vs(k);
for (auto& s : vs)
cin >> s;
trie_insert(vs);
}
print_trie(0, 0);
return 0;
}
배열로 짠 트라이로 구현한 코드입니다. 노드 개수 상한은 N*K=15000 거기에 루트 + 1=15001로 설정했습니다.
맞은사람 코드를 보다 보니 배열로 짜는것보다 훨씬 깔끔하면서 메모리도 덜쓰고, 동적할당은 하지 않는 어썸한 코드가 있어서 링크를 남깁니다
저보다 훨씬 깔끔한 코드(shiftpsh님 코드): https://www.acmicpc.net/source/17311258
반응형
'Online Judge > 백준' 카테고리의 다른 글
[백준][C++] 17390: 이건 꼭 풀어야 해! (0) | 2020.07.17 |
---|---|
[백준][C++] 14425: 문자열 집합 (0) | 2020.07.16 |
[백준][C++] 5052: 전화번호 목록 (0) | 2020.07.16 |
[백준][C++] 14582: 오늘도 졌다 (0) | 2020.07.16 |
[백준][C++] 11946: ACM-ICPC (0) | 2020.07.16 |