반응형

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
반응형

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

 

7432번: 디스크 트리

갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/417

 

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

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

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열을 trie에 insert 합니다.

 

2. root부터 오름차순으로 폴더이름을 출력합니다.

 

[ 소스코드 ]

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
75
76
#include<iostream>
#include<vector>
#include<map>
#include<string>
 
using namespace std;
 
int N;
 
struct Trie {
    map<string, Trie *> m;
 
    void insert(vector<string> vect, int level) {
        if ((int)vect.size() > level) {
            if (!m.count(vect[level])) {
                m[vect[level]] = new Trie;
            }
 
            m[vect[level]]->insert(vect, level + 1);
        }
    }
 
    void print(int level) {
        if (m.empty()) return;
        for (auto& next : m) {
            for (int i = 0; i < level; i++) {
                cout << ' ';
            }
            cout << next.first << '\n';
            next.second->print(level + 1);
        }
    }
};
 
vector <string> split(string str) {
    vector <string> ret;
    
    int s = 0;
    int e = 0;
 
    while (1) {
        e = str.find('\\', s);
        if (e == -1) {
            ret.push_back(str.substr(s, str.size() - s));
            break;
        }
        else {
            ret.push_back(str.substr(s, e - s));
            s = e + 1;
        }
    }
 
    return ret;
}
 
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++) {
        string str;
        cin >> str;
        
        vector<string> vect = split(str);
 
        root->insert(vect, 0);
    }
 
    root->print(0);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1245번 - 농장 관리 (C++)  (0) 2023.07.26
[ 백준 ] 16934번 - 게임 닉네임 (C++)  (0) 2023.07.25
[ 백준 ] 16929번 - Two Dots (C++)  (0) 2023.07.23
[ 백준 ] 2800번 - 괄호 제거(C++)  (0) 2023.07.22
[ 백준 ] 1990번 - 소수인팰린드롬(C++)  (0) 2023.07.21
반응형

1. 트라이(Trie)

 

트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다.

 

2. 트라이(Trie) 동작 원리

먼저 그림을 통해 살펴보도록 하겠습니다.

다음 그림은 문자열 {"jade", "japp", "an", "answer"}를 트라이(Trie)로 구현한 것입니다.

 

 

3. 트라이(Trie) 구현

트라이의 노드는 자손 노드를 가리키는 포인터 배열과, 문자열의 끝인지를 나타내는 bool 변수로 구성되어 있습니다.

보통 영어 소문자로만 이루어딘 경우가 대부분이기 때문에 배열의 크기를 26으로 선언합니다.

동적으로 메모리를 할당하기 때문에 delete로 해제해주는 것이 매우 중요합니다.

이제 문자열을 트라이에 넣어주는 함수에 대해 알아보겠습니다.

이미 트라이에 해당 문자에 해당하는 노드가 있다면 따라가고, 그렇지 않다면 새로 만들어줍니다.

문자열의 끝에 도달하면 end의 값을 true로 바꾸어줍니다.

마지막으로 트라이에서 찾고자 하는 문자열이 있는지 탐색하는 함수에 대해 알아보겠습니다.

만약 다음 문자로 가는 노드가 존재하지 않는다면 존재하지 않는 단어입니다.

또한, 문자열의 끝에 도달했을 때 end의 값이 true가 아니라면 존재하지 않는 단어입니다.

 

[ 소스코드 ]

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
struct trie {
    trie* ch[26];
    bool end;
 
    trie() {
        end = false;
        for (int i = 0; i < 10; i++) ch[i] = NULL;
    }
    ~trie() {
        for (int i = 0; i < 10; i++) {
            if(num[i]) delete ch[i];
        }
    }
 
    void insert(const char* c) {
        if (!*c) {
            this->end = true;
            return;
        }
 
        int now = *c - '0';
        if (!num[now]) num[now] = new trie;
        num[now]->insert(c + 1);
    }
 
    bool find(const char* c) {
        if (!*c || end) {
            return true;
        }
 
        int now = *c - '0';
        if (!num[now]) return false;
        return num[now]->find(c + 1);
    }
};
 
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'자료구조' 카테고리의 다른 글

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)  (0) 2023.08.07
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)  (0) 2023.05.04
[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)  (0) 2023.01.16
[ 자료구조 ] 희소 배열(Sparse Table)  (0) 2022.08.07
[ 자료구조 ] 세그먼트 트리 (Segment Tree)  (0) 2022.07.02

+ Recent posts

티스토리툴바