[C++] 백준 16934번: 게임 닉네임

문제 링크

16934번: 게임 닉네임

문제 요약

어떤 게임에서 유저의 닉네임을 기반으로 내부적으로 저장할 별칭을 만든다. 별칭을 생성하는 규칙은 다음과 같다.
1. 유저 닉네임의 접두사 중 가장 짧은 것을 사용하되, 이 접두사는 이전에 가입한 다른 닉네임의 접두사가 되면 안된다.
2. 만약 그런 별칭이 없다면, 별칭 뒤에 숫자를 붙인다. ex) baekjoon, baekjoon2, baekjoon3...
어떤 닉네임이 주어지면 해당 닉네임의 별칭을 출력해야 한다.

접근 방법

접두사를 이용한 별칭을 만들고, 별칭이 앞서 입력된 다른 별칭의 접두사가 되는지 확인을 해야 합니다.

트라이를 이용해서 쉽게 풀 수 있습니다.

먼저 트라이 클래스를 만들어야 합니다. 클래스 안에는 알파벳 26개에 대응되는 트라이 포인터 변수와 현재 노드에서 끝이 나는 문자열의 수를 세기 위한 cnt 변수를 선언합니다.

class Trie {
public:
    int cnt = 0;
    Trie *node[26]{};
};

그리고 insert 함수를 정의해줍니다. insert 함수는 문자열 str을 참조자로, 그리고 현재 문자열 내 인덱스 위치를 알기 위한 idx를 변수로 받습니다.

string Trie::insert(string &str, int idx) {
    if (idx == str.size()) {
        return (++cnt == 1 ? str : str + to_string(cnt));
    }

    if (node[str[idx] - 'a'] == nullptr) {
        node[str[idx] - 'a'] = new Trie();
        node[str[idx] - 'a']->insert(str, idx + 1);
        return str.substr(0, idx + 1);
    }

    return node[str[idx] - 'a']->insert(str, idx + 1);
}

문자열 내 다음 문자에 따라서 insert 함수를 재귀호출 해주면 됩니다. 만약, 방문하고자 하는 node가 NULL이라면, 현재까지 방문한 문자열은 어떠한 문자열의 접두사도 되지 않음을 의미합니다. 따라서 재귀호출을 마저 진행해주고, NULL을 만나기 전까지의 부분 문자열을 반환을 해주면 됩니다.

만약 문자열의 끝까지 도착하게 되면 cnt를 1 증가시켜 줍니다. 여기서 끝난 문자열이 하나 더 있다는 뜻입니다. 그리고 cnt가 1이라면 현재 문자열을 그대로 반환해주면 되고, 2 이상이라면 현재 문자열 + cnt를 반환해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

class Trie {
public:
    int cnt = 0;

    Trie *node[26]{};

    Trie();

    string insert(string &str, int idx);

    void clear();
};

Trie::Trie() {
    for (auto &i: node) {
        i = nullptr;
    }
}

string Trie::insert(string &str, int idx) {
    if (idx == str.size()) {
        return (++cnt == 1 ? str : str + to_string(cnt));
    }

    if (node[str[idx] - 'a'] == nullptr) {
        node[str[idx] - 'a'] = new Trie();
        node[str[idx] - 'a']->insert(str, idx + 1);
        return str.substr(0, idx + 1);
    }

    return node[str[idx] - 'a']->insert(str, idx + 1);
}

void Trie::clear() {
    for (auto &i: node) {
        if (i != nullptr) {
            i->clear();
            delete i;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    Trie *root = new Trie();

    while (n--) {
        string str;
        cin >> str;
        cout << root->insert(str, 0) << '\n';
    }

    root->clear();
    return 0;
}