단어를 루트에 삽입하면서 하나씩 출력한다. 그러다가 다음 알파벳이 자식 노드로 존재하지 않으면, print를 false로 변경하고 재귀호출한다. print가 true인 경우에만 알파벳을 출력한다.
같은 닉네임으로 가입한 유저를 숫자로 구분하기 위해 map<string, int> 사용.
#include <bits/stdc++.h>
using namespace std;
struct Trie {
Trie* t[26];
int cnt;
bool end;
Trie() {
memset(t, 0, sizeof(t));
// end = false;
}
~Trie() {
for (int i = 0; i < 26; i++) {
if (t[i]) delete t[i];
}
}
void insert(string& s, int idx, bool print) {
if (idx == s.length()) {
// end = true;
return;
}
if (print) cout << s[idx];
if (!t[s[idx]-'a']) {
t[s[idx]-'a'] = new Trie();
print = false;
}
t[s[idx]-'a']->insert(s, idx+1, print);
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
Trie root;
map<string, int> m;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
root.insert(s, 0, true);
if (m[s]) cout << ++m[s];
else m[s] = 1;
cout << '\n';
}
return 0;
}
아 게임하고싶다