문제 URL : https://www.acmicpc.net/problem/16934
16934번: 게임 닉네임
첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고,
www.acmicpc.net
문제접근법 : 트라이와 해시를 이용한 문제입니다.
해당 문자열을 받은후 한번이라도 나왔던 문자열이라면 별칭을 부여할수없으니 그문자열에 나왔던숫자 만큼 +1 해서 출력해주면되고 확인후 나오지 않았던 문자열이라면
트라이에 문자열을 삽입합니다. 이때 해당 문자열에서 한번이라도 나온적없는 문자열이면 바로 출력해주고 트라이구조를 계속해서 만들어 주는 문제기때문에 트라이 구조를 조금만안다면 쉽게 풀수 있는 문제입니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
//By 콩순이냉장고
#include <iostream>
#include <unordered_map>
#include<cstring>
#include <string>
using namespace std;
unordered_map<string, int> visit;
int n;
struct trie {
trie* children[26];
bool terminal;
trie() : terminal(false) {
memset(children, 0, sizeof(children));
}
~trie() {
for (int i = 0; i < 26; i++) {
if (children[i])
delete children[i];
}
}
void insert(string& s, int idx = 0,bool ismake=true) {
//ismake는 별칭을 부여했는지
if (s[idx] == 0) {
terminal = true;
if (ismake) {
cout << s << "\n";
ismake = false;
}
return;
}
int next = s[idx] - 'a';
if (children[next] == NULL) {
children[next] = new trie();
if (ismake) {
string ans(s.begin(), s.begin() + idx+1);
cout << ans << "\n";
ismake = false;
}
}
children[next]->insert(s, idx + 1,ismake);
}
};
void input() {
cin >> n;
}
void solve() {
string s;
trie tr;
for (int i = 0; i < n; i++) {
cin >> s;
if (visit[s] == 0) {
tr.insert(s);
}
else
cout << s << visit[s] + 1 << "\n";
visit[s]++;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 혹은 논리적인 오류등 어떤질문이라도 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 14426 접두사 찾기 (0) | 2021.07.16 |
|---|---|
| 백준 12904 A와 B (0) | 2021.07.15 |
| 백준 17609 회문 (0) | 2021.07.05 |
| 백준 5582 공통 부분 문자열 (0) | 2021.07.05 |
| 백준 2531 회전 초밥 (0) | 2021.07.02 |
