백준 16934번 게임 닉네임

백준 16934번: 게임 닉네임

아이디어

단어를 루트에 삽입하면서 하나씩 출력한다. 그러다가 다음 알파벳이 자식 노드로 존재하지 않으면, 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;
}

여담

아 게임하고싶다