[G3] 백준 16934번 게임 닉네임 C++ 트라이, 문자열, 해시맵

리뷰

 

트라이를 사용해 유저가 가입한 순서대로 닉네임이 주어졌을 때, 각 유저의 별칭을 구하는 문제

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

 

전역 변수

• Trie : 트라이를 구현할 구조체 동일한 닉네임이 들어올 수 있으므로 cnt라는 변수를 업데이트 해줘야 한다.
• root : 트라이의 루트를 나타낼 Trie타입 구조체
• n : 입력 받을 게임 닉네임의 개수

 

함수

1. insert

void insert(Trie* node, const string& str)

 

1. 트라이에 게임 닉네임을 입력하고, 별칭을 출력해 주는 함수
2. 함수 호출 시 flag를 통해 별칭을 출력했는지 여부를 체크해 준다. 기본값은 1이다.
3. 입력 받은 문자열을 순회하며 다음 노드가 있는지 체크해 준다.
4. 만약 다음 노드가 존재하지 않을 시 현재까지의 문자열을 별칭으로 출력해 주고 flag를 0으로 바꿔준다.
5. 이후 새로운 노드를 추가해 주며 별칭을 기록해 준다.
6. 만약 문자열의 끝까지 노드를 추가 했음애도 flag가 1인 상태라면
7. 현재 문자열을 그대로 출력해 준다, 이후 현재 노드의 cnt개수에 따라 숫자를 추가로 출력해 주면 된다.
8. 위 작업이 완료된 경우 현재 노드의 cnt를 증가시켜 준다.

 

문제풀이

1. n값을 입력 받은 뒤 n번의 반복문을 시작하고, 각각 게임 닉네임을 입력 받아준다.
2. insert함수를 통해 root부터 게임 닉네임의 각 문자를 트라이에 삽입해 준다.

 

참고 사항

• 문자열을 insert하면서 트라이에 존재하지 않는 노드가 나온 경우 별칭이 완성된 상태이다.
• 만약 문자열을 모두 순회할때까지 별칭이 완성되지 않았다면 문자열 자체가 별칭이 된다.
• 만약 동일한 닉네임이 있을 경우 cnt를 통해 별칭의 개수를 세어주어야 한다.
• cnt가 0일 경우에는 상관 없지만 1이상일 경우 추가로 출력해 준다.

 

정답 코드

#include<iostream>
#include<unordered_map>

using namespace std;

struct Trie {
	unordered_map<char, Trie*> child;
	int cnt;
	Trie() {
		cnt = 0;
	}
};

Trie* root = new Trie();

int n;

void insert(Trie* node, const string& str) {
	Trie* cur = node;
	int flag = 1;
	for (int i = 0; i < str.size(); i++) {
		int idx = str[i] - 'a';
		if (!cur->child[idx]) {
			if (flag) {
				flag = 0;
				cout << string(str.begin(), str.begin() + i + 1) << "\n";
			}
			cur->child[idx] = new Trie();
		}
		cur = cur->child[idx];
	}
	if (flag) {
		cout << str;
		if (cur->cnt) cout << cur->cnt + 1;
		cout << "\n";
	}
	cur->cnt++;
}

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

	cin >> n;
	while (n--) {
		string s; cin >> s;
		insert(root, s);
	}
}