문제

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

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

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

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

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

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

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

입력

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

출력

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

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

풀이

문제를 잘 이해해야한다.

• 출력한 모든 별칭을 저장해야한다. 만약 중복되는 별칭을 출력하려면 뒤에 숫자를 2, 3, 4... 를 붙여서 출력해야한다.
• 입력문자열의 부분문자열을 별칭으로 출력할것이다.
• 부분문자열과 이전 Trie구조에 포함된 문자열들의 부분문자열이 중복되지않는 최소길이로 출력해야한다.

처음에는 Trie구조체에 insert하기전에 외부에서 입력문자열을 앞에서부터하나씩 잘라낸 부분문자열을 Trie구조체에 check하는 함수로 확인하도록했는데
알게모르게 런타임에러가나서,

Trie구조체의 insert함수에 별칭을 출력하도록하는 코드를 추가하여 작성하여 풀었다.

1. Trie구조체 변수, 생성자
   

2. Trie구조체 insert함수
   입력문자열을 받아서 재귀적호출로, Trie구조내로 문자열을 한 문자씩 편입시키며 동시에 조건에 맞게 출력하는 부분이다.
   재귀적 구조의 함수를 구현하며 느낀것이

• 어떤 상태에대한 값을 전달해야하면 매개변수로 전달한다
  이말은즉, printable라는 어떤 상태를 표현하는 값을 전역변수로 두거나 하지말고 매개변수로 설정하여 보내면 편리하다는것

또, 문자열 슬라이싱할때, line108 처럼 문자열의 주소 S.begin()을 이용하면 편리하게 가능하다는것.

그외의 구조는 이전 블로그포스팅 (>> https://velog.io/@cldhfleks2/Trie)에서 다뤘으므로 자세한내용은 참고하라.

3. 입력받고, 별칭이존재하면 뒤에 숫자를 붙여 출력하도록하는 프로그램의 메인
   line132 에따라 이미 사용한 별칭이 존재하느냐 안하느냐에 따라 insert함수를 호출여부를 결정했다.
   당연히 insert함수에 출력부분이있으니, insert함수를 호출안했으면 입력문자열에 정수를 붙여서 출력해주었다.
   그리고 line136으로 별칭을 map<string, int>에 추가해주었다.
   

아래는 전체 코드이다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define mp std::make_pair 
#define mt std::make_tuple
#define dq std::deque
#define pq std::priority_queue
#define sw std::swap
#define ts(x) std::to_string(x)
#define tc() c_str()
#define sc(x, ...) scanf(x, ##__VA_ARGS__) 
#define pr(x, ...) printf(x, ##__VA_ARGS__) 
#define ins(x) insert(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define PB() pop_back()
#define PF() pop_front()
#define ph(x) push(x)
#define TT() top()
#define PP() pop()
#define BB() back()
#define FF() front()
#define cls() clear()
#define emp() empty()
#define len(x) x.length()
#define sz(x) ((int)x.size()) //컨테이너에서 사용
#define ms(a) memset(a, 0, sizeof(a)) //0으로 초기화
#define rep(i, n) for(int i = 0; i < n ; i++)
#define rrep(i, r, n) for(int i = r; i < n ; i++)
#define rrrep(i, r, n) for(ll i = r; i < n ; i++)
#define _rrep(i, r, n) for(int i = r; i >= n; i--)
#define _rrrep(i, r, n) for(ll i = r; i >= n; i--)
#define each(x, a) for (auto& x: a)
#define all(x) x.begin(),x.end() //STL에서 전체 처리할때 사용
#define range(x, r, n) x.begin() + r, x.begin() + n //STL에서 구간설정
#define ct continue
#define br break
#define rt return
#define _TYF typedef //코드줄이기
#define _UG using
#define _TCE template <class T> inline
//#define MAX 
const int IMAX = INT32_MAX; const int IMIN = INT32_MIN;
const long long LMAX = LLONG_MAX; const long long LMIN = LLONG_MIN;
const long double PI = 3.141592653589793238462643383279502884197;
_UG std::vector; _UG std::stack; _UG std::queue; _UG std::tuple; _UG std::set; _UG std::list; _UG std::bitset; _UG std::string; _UG std::pair; _UG std::greater;
_UG std::tie; _UG std::sort; _UG std::max_element; _UG std::min_element; _UG std::fill; _UG std::stoi; _UG std::stod; _UG std::stof; _UG std::stol; _UG std::stold; _UG std::stoll; _UG std::stoul; _UG std::stoull;
//_UG std::max; //_UG std::min; //_UG std::map;
_TYF long long ll; _TYF unsigned long long ull;
_TYF pair<int, int> pii; _TYF pair<double, int> pdi; _TYF pair<int, double> pid; _TYF pair<double, double> pdd; _TYF pair<int, ll> pil;
_TYF pair<ll, int> pli; _TYF pair<ll, ll> pll; _TYF pair<ull, ull> pullull; _TYF pair<int, char> pic; _TYF pair<char, int> pci;
_TYF pair<char, char> pcc; _TYF pair<long, char> plc; _TYF pair<char, long> pcl; _TYF pair<ll, char> pllc; _TYF pair<char, ll> pcll;
_TYF pair<ull, char> pullc; _TYF pair<char, ull> pcull; _TYF pair<int, string> pis; _TYF pair<string, int> psi; _TYF pair<long, string> pls;
_TYF pair<string, long> psl; _TYF pair<ll, string> plls; _TYF pair<string, ll> psll; _TYF pair<ull, string> pulls;
_TYF pair<string, ull> psull; _TYF pair<string, string> pss;
_TYF tuple<int, int, int> tiii; _TYF tuple<int, int, int, int> tiiii;
_TYF tuple<ll, ll, ll> tlll; _TYF tuple<ll, ll, ll, ll> tllll;
_TYF vector<string> vs; _TYF queue<string> qs; _TYF stack<string> ss; _TYF dq<string> dqs; _TYF pq<string> pqs; _TYF dq<string> dqs;
_TYF vector<char> vc; _TYF queue<char> qc; _TYF stack<char> sc; _TYF dq<char> dqc; _TYF pq<char> pqc; _TYF dq<char> dqc;
_TYF vector<int> vi; _TYF queue<int> qi; _TYF stack<int> si; _TYF dq<int> dqi; _TYF pq<int> pqi; _TYF dq<int> dqi;
_TYF vector<pii> vii; _TYF queue<pii> qii; _TYF stack<pii> sii; _TYF dq<pii> dqii; _TYF pq<pii> pqii; _TYF dq<pii> dqii;
_TYF vector<tiii> viii; _TYF queue<tiii> qiii; _TYF stack<tiii> siii; _TYF dq<tiii> dqiii; _TYF pq<tiii> pqiii; _TYF dq<tiii> dqiii;
_TYF vector<tiiii> viiii; _TYF queue<tiiii> qiiii; _TYF stack<tiiii> siiii; _TYF dq<tiiii> dqiiii; _TYF pq<tiiii> pqiiii; _TYF dq<tiiii> dqiiii;
_TYF vector<pll> vll; _TYF queue<pll> qll; _TYF stack<ll> sll; _TYF dq<pll> dqll; _TYF pq<pll> pqll; _TYF dq<pll> dqll;
_TYF vector<tlll> vlll; _TYF queue<tlll> qlll; _TYF stack<tlll> slll; _TYF dq<tlll> dqlll; _TYF pq<tlll> pqlll; _TYF dq<tlll> dqlll;
_TYF vector<tllll> vllll; _TYF queue<tllll> qllll; _TYF stack<tllll> sllll; _TYF dq<tllll> dqllll; _TYF pq<tllll> pqllll; _TYF dq<tllll> dqllll;
_TCE T sq(T num) { rt num* num; }//제곱함수
_TCE T GCD(T num1, T num2) { if (num2 == 0) rt num1; rt GCD(num2, num1 % num2); }
_TCE T LCM(T num1, T num2) { if (num1 == 0 || num2 == 0) rt num1 + num2; rt num1* (num2 / GCD(num1, num2)); }
//STL 전용 초기화 함수들 ( ms~~ )
_TCE void msq(T& a) { while (!a.empty()) a.PP(); }//queue clear
_TCE void msv(T& a) { a.cls(); }//vector clear
_TCE void msdq(T& a) { a.cls(); }//deque clear
_TCE void msm(T& a) { a.cls(); }//map clear
_TCE void mss(T& a) { while (!a.empty()) a.PP(); }//stack, set clear
_TCE void mspq(T& a) { while (!a.empty()) a.PP(); }//priority_queue clear
//pii operator - (pii a, pii b) { rt pii(a.first - b.first, a.second - b.second); }
//bool operator <= (pii a, pii b) { rt a.first <= b.first && a.second <= b.second; } 
//bool operator >= (pii a, pii b) { rt a.first >= b.first && a.second >= b.second; } 
//bool operator < (pii a, pii b) { if (a == b) return false; rt a <= b; } 
//bool operator > (pii a, pii b) { if (a == b) return false; rt a >= b; }

int N;
std::map<string, int> nickname;

struct Trie {
private:
	std::map<char, Trie*> node;
	bool finished;

public:
	Trie() : node(), finished(false) {}

	//입력문자열을 Trie구조로 편입하며 동시에 한번은 출력하는 함수
	void insert(string &str, int idx=0, bool printable=false) {
		if (idx == str.length()) { //입력문자열의 끝 다음순번이 오면
			finished = true; //종료체크
			if (!printable) { //지금껏 문자열이 출력안됬으면 입력문자열 전체를 출력
				pr("%s\n", str.tc());
				printable = true;
			}
			return;
		}

		//존재하지 않는 접두사를 발견했는데, 지금껏출력을 안했을때 
		//지금까지의 부분문자열을 출력함
		if (node[str[idx]] == nullptr && !printable) {
			node[str[idx]] = new Trie();
			string S(str.begin(), str.begin() + idx + 1);
			pr("%s\n", S.tc());
			printable = true;
		}

		//이미 출력한상태면 새로 Trie객체만 만듬
		if (node[str[idx]] == nullptr && printable)
			node[str[idx]] = new Trie();
		
		//재귀적 호출
		node[str[idx]]->insert(str, idx + 1, printable);
	}
};

//프로그램 메인 로직
void func() {
	Trie trie;
	sc("%d", &N);

	rep(_, N) {
		char c[11];
		sc("%s", c);
		string str(c); //입력문자열(별칭)

		if (nickname[str] == 0) //별칭이 존재하지않으면 
			trie.insert(str); //trie구조에 추가하며 접두사를 별칭으로 사용
		else //별칭이 존재하면
			pr("%s%d\n", str.tc(), nickname[str] + 1); //별칭 + 존재갯수를 붙여서 출력
		nickname[str]++; //별칭에 추가
	}
}

int main(void) {
	func();

	rt 0;
}