[BaekJoon] 16934번 - 게임 닉네임 [Java][C++]

문제 링크

---

1. 문제 풀이

각 유저의 별칭을 찾는 문제로 별칭은 이전에 가입한 닉네임의 접두사가 아니면서 가장 짧아야하며 가능한 별칭이 없으면 같은 닉네임으로 가입한 사람의 수를 기반으로 지어야 한다. 트라이 자료구조를 활용해 해당 닉네임에 대해 검색 후 삽입으로 처리하면 되며 검색에서는 다음 노드가 존재하지 않는 순간 지금까지 방문한 노드들도 이루어진 문자열이 별칭이 된다. 모든 노드를 방문하게 되면 가능한 별칭이 없게 되는데 맵을 활용해서 동일한 닉네임으로 가입한 사람의 수를 계산했다가 이때 활용하면 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int MX = 1 + 100000 * 10;
    static final int ROOT = 0;
    static int unused = ROOT + 1;
    static int[][] nxt = new int[MX][26];
    static Map<String, Integer> map = new HashMap<>();  // key를 닉네임으로 가입한 유저의 수(value)

    static void insert(String s) {
        int cur = ROOT;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (nxt[cur][idx] == 0) nxt[cur][idx] = unused++;
            cur = nxt[cur][idx];
        }
    }

    static String find(String s) {
        StringBuilder prefix = new StringBuilder();
        int cur = ROOT;
        for (char c : s.toCharArray()) {
            prefix.append(c);
            int idx = c - 'a';
            if (nxt[cur][idx] == 0) return prefix.toString();
            cur = nxt[cur][idx];
        }

        if (map.containsKey(s)) prefix.append(map.get(s) + 1);
        return prefix.toString();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            String s = br.readLine();

            sb.append(find(s)).append("\n");
            insert(s);
            map.put(s, map.getOrDefault(s, 0) + 1);
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 1 + 100000 * 10;
const int ROOT = 0;
int unused = ROOT + 1;
int nxt[MX][26];
unordered_map<string, int> mp;  // key를 닉네임으로 가입한 유저의 수(value)

void insert(string& s) {
    int cur = ROOT;
    for (char c : s) {
        int idx = c - 'a';
        if (nxt[cur][idx] == 0) nxt[cur][idx] = unused++;
        cur = nxt[cur][idx];
    }
}

string find(string& s) {
    string prefix = "";
    int cur = ROOT;
    for (char c : s) {
        prefix += c;
        int idx = c - 'a';
        if (nxt[cur][idx] == 0) return prefix;
        cur = nxt[cur][idx];
    }

    if (mp[s] > 0) prefix += to_string(mp[s] + 1);
    return prefix;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    while (n--) {
        string s;
        cin >> s;

        cout << find(s) << '\n';
        insert(s);
        mp[s]++;
    }
}

---