문제 출처

1. 문제설명

  • 문자열이 주어질 때 별명을 지으면 된다.
  • 별명 짓는 규칙
    • 가장 짧은 접두어로 짓는다.
    • 접두어를 찾았는데 별명이 있다면 그 다음 글자까지 붙여 접두어를 만든다.
      • 붙인 문자열이 어떤 문자열의 접두어면 안된다.
    • 현재 입력된 문자열로 된 별명이 있다면 숫자 2를 붙이고, 숫자까지 이미 있다면 숫자를 증가시킨다.
  • 문제 분류
    • Data Structure, String, Tree, set and map using Hash, Trie


2. 알고리즘 설계

  • Trie + map 자료구조로 해결할 수 있었다.
    • map은 번호 짓는 규칙 때문에 필요하다.
  • Trie에서 문자열을 찾는데 다음 위치가 -1 이라면 최초인 것이다.
    • 이 때까지의 문자열을 리턴해주면 된다.
    • 리턴을 하는데 현재 문자열이 이미 맵에 저장되어 있다면, 개수를 붙여 리턴한다.


3. 전체 코드

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

const int MX = 100'000 * 10 + 5;
const int ROOT = 1;

int unused = ROOT + 1;
int nxt[MX][26];
unordered_map<string, int> user;

int c2i(char c) { return c - 'a'; }

void insert(string& s) {
	int cur = ROOT;
	for(auto c : s) {
		if(nxt[cur][c2i(c)] == -1)
			nxt[cur][c2i(c)] = unused++;
		cur = nxt[cur][c2i(c)];
	}
}

string find(string& s) {
	string tmp = "";
	int cur = ROOT;
	for(auto c : s) {
		tmp += c;
		if(nxt[cur][c2i(c)] == -1) return tmp;
		cur = nxt[cur][c2i(c)];
	}
	if(user[s] > 1) tmp += to_string(user[s]);
	return tmp;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	for(int i=0; i<MX; i++)
		fill(nxt[i], nxt[i]+26, -1);

	int n;
	cin >> n;
	for(string s; n--;) {
		cin >> s;
		user[s]++;
		cout << find(s) << '\n';
		insert(s);
	}
}