반응형

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

+ Recent posts

티스토리툴바