반응형

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

 

16934번: 게임 닉네임

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

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/417

 

[ 자료구조 ] 트라이(Trie)

1. 트라이(Trie) 트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다. 2. 트라이(Trie) 동작 원리 먼저 그림을 통해 살펴보도록 하겠습니다. 다음 그림은 문자열 {"jade", "ja

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열을 print를 통해 새로운 문자가 나오거나 문자열의 끝이 오면 해당 문자열을 출력합니다.

 

2. trie에 해당 문자열을 insert 합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
 
struct Trie {
    Trie* arr[26];
    int end;
 
    Trie() {
        for (int i = 0; i < 26; i++) {
            arr[i] = NULL;
        }
 
        end = 0;
    }
 
    ~Trie() {
        for (int i = 0; i < 26; i++) {
            if (arr[i]) delete arr[i];
        }
    }
 
    void insert(const char* ch) {
        char temp = *ch - 'a';
        if (!*ch) {
            end++;
            return;
        }
 
        if (arr[temp] == NULL) arr[temp] = new Trie;
        arr[temp]->insert(ch + 1);
    }
 
    void print(const char* ch) {
        char temp = *ch - 'a';
        if (!*ch) {
            if (end) {
                cout << end + 1;
            }
            cout << '\n';
            return;
        }
 
        cout << *ch;
 
        if (arr[temp] == NULL) {
            cout << '\n';
            return;
        }
 
        arr[temp]->print(ch + 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    Trie* root = new Trie;
 
    for (int i = 0; i < N; i++) {
        char ch[11];
        cin >> ch;
 
        root->print(ch);
        root->insert(ch);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 15558번 - 점프 게임 (C++)  (0) 2023.07.27
[ 백준 ] 1245번 - 농장 관리 (C++)  (0) 2023.07.26
[ 백준 ] 7432번 - 디스크 트리 (C++)  (0) 2023.07.24
[ 백준 ] 16929번 - Two Dots (C++)  (0) 2023.07.23
[ 백준 ] 2800번 - 괄호 제거(C++)  (0) 2023.07.22

+ Recent posts

티스토리툴바