[BOJ/Gold 2] 백준 16934 게임 닉네임(C++)

문제 링크

https://www.acmicpc.net/problem/16934

16934번: 게임 닉네임

 

문제

스타트링크에서 매우 재미있는 게임을 만들었다. 이 게임은 정말 재미있다.

게임에는 유저가 접속하는 기능이 있고, 각 유저는 가입할 때, 자신의 닉네임을 정해야 한다. 닉네임은 알파벳 소문자로만 이루어져 있고, 두 유저가 같은 닉네임을 정하는 것도 가능하다.

이 게임은 유저의 닉네임을 이용해서 내부에 저장할 별칭을 만든다. 별칭은 유저에게 보여지지는 않고, 내부에서만 사용된다. 저장 공간을 최소로 하기 위해서 별칭의 길이를 최소로 하려고 한다.

별칭은 유저 닉네임의 접두사(Prefix) 중에서 가장 길이가 짧은 것을 사용한다. 이때, 접두사가 이전에 가입한 닉네임의 접두사가 아니어야 한다. 가능한 별칭이 없는 경우에는 유저가 가입한 시점까지 같은 닉네임으로 가입한 사람의 수 x를 계산해야 한다. x가 1인 경우에는 닉네임을 별칭으로 사용하고, x가 2 이상인 경우에는 닉네임의 뒤에 x를 붙여서 별칭으로 사용한다.

예를 들어, 닉네임을 "baekjoon"으로 정한 유저가 가입하면, 이 유저의 별칭은 "b"가 된다. 

그 다음, 닉네임이 "startlink"로 정한 유저가 가입하면, 이 유저의 별칭은 "s"이다. "bakejoon"이 닉네임인 유저가 가입하면, 별칭은 "bak"가 되고, "beakjoon"인 유저가 가입하면, 별칭은 "be"가 된다. 마지막으로 "baekjoon"으로 유저가 가입하면 별칭은 "baekjoon2"가 된다.

유저가 가입한 순서대로 닉네임이 주어졌을 때, 각 유저의 별칭을 구해보자. 위의 규칙을 이용해 별칭을 정하면 두 유저가 같은 별칭을 갖는 것도 가능하다.

입력

첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고, 길이는 10을 넘지 않는다.

출력

유저가 가입한 순서대로 별칭을 한 줄에 하나씩 출력한다.

예제 입력 1

5
baekjoon
startlink
bakejoon
beakjoon
baekjoon

예제 출력 1

b
s
bak
be
baekjoon2

예제 입력 2

7
codeplus
startlink
beakjoon
baek
baekjoon
baek
codingwiki

예제 출력 2

c
s
b
ba
baekj
baek2
codi

예제 입력 3

6
abcd
ab
ab
a
a
ab

예제 출력 3

a
ab
ab2
a
a2
ab3

알고리즘 분류

• 자료 구조
• 트라이

풀이

닉네임을 입력받고, 해당 닉네임의 존재 유무를 트라이를 통해 탐색한다.

트라이의 특정 branch의 끝까지 도달했다면, 닉네임 그 자체를 별칭으로 삼는다.

이 때 이미 닉네임 그 자체를 별칭으로 삼은 유저가 존재한다면, 뒤에 해당 닉네임을 가진 유저 수 + 1만큼의 숫자를 추가해 별칭으로 정한다.

물론 해당 닉네임 그 자체를 별칭으로 삼은 유저가 존재하지 않는다면 그냥 닉네임 그 자체를 별칭으로 정한다.

트라이의 특정 branch를 탐색하다가 불일치하는 문자가 존재한다면, 닉네임의 시작부터 해당 문자까지를 별칭으로 정한다.

마지막으로 결정한 별칭을 출력하고 입력받은 닉네임을 트라이에 insert한다.

이것을 N번 반복한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#define MAX 26
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct TRIE{
    TRIE* Child[MAX];
    bool isEnd;

    TRIE() : isEnd(false) {
        fill(Child, Child + MAX, nullptr);
    }

    ~TRIE() {
        for (int i = 0; i < MAX; i++) {
            if (Child[i]) {
                delete Child[i];
            }
        }
    }

    void insert_Name(string Name) {
        TRIE* NowTrie = this;

        for (int i = 0; i < Name.size(); i++) {
            int Now = Name[i] - 'a';
            if (!NowTrie->Child[Now]) {
                NowTrie->Child[Now] = new TRIE;
            }
            NowTrie = NowTrie->Child[Now];
        }
        NowTrie->isEnd = true;
    }
};

int N;
string S;
unordered_map<string, int> UM;

void find_Answer(TRIE* Root) {
    TRIE* NowTrie = Root;
    for (int i = 0; i < S.size(); i++) {
        int Now = S[i] - 'a';
        if (NowTrie->Child[Now]) {
            NowTrie = NowTrie->Child[Now];
        }
        else {
            string Nick = "";
            for (int j = 0; j <= i; j++) {
                Nick += S[j];
            }
            if (UM[Nick] == 0) {
                cout << Nick << "\n";
            }
            else {
                cout << Nick << UM[Nick] + 1 << "\n";
            }
            return;
        }
    }
    if (UM[S] == 0) {
        cout << S << "\n";
    }
    else {
        cout << S << UM[S] + 1 << "\n";
    }
}

void input() {
    TRIE* Root = new TRIE();
    cin >> N;
    while (N--) {
        cin >> S;
        find_Answer(Root);
        UM[S]++;
        Root->insert_Name(S);
    };
    delete Root;
}

int main() {
    FASTIO
    input();

    return 0;
}