반응형

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

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

 

5052번: 전화번호 목록

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/417

 

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

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

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열이 trie에 있는지 체크하고, 있다면 NO를 출력하고, 그렇지 않다면 YES를 출력합니다.

 

[ 소스코드 ]

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>
 
using namespace std;
 
int n, t;
 
struct trie {
    trie* num[10];
    bool end;
 
    trie() {
        end = false;
        for (int i = 0; i < 10; i++) num[i] = NULL;
    }
    ~trie() {
        for (int i = 0; i < 10; i++) {
            if(num[i]) delete num[i];
        }
    }
 
    void insert(const char* ch) {
        if (!*ch) {
            this->end = true;
            return;
        }
 
        int now = *ch - '0';
        if (!num[now]) num[now] = new trie;
        num[now]->insert(ch + 1);
    }
 
    bool find(const char* ch) {
        if (!*ch || end) {
            return true;
        }
 
        int now = *ch - '0';
        if (!num[now]) return false;
        return num[now]->find(ch + 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    while (t--) {
        trie* root = new trie;
        bool flag = true;
 
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            char arr[11];
            cin >> arr;
 
            if (root->find(arr)) {
                if(flag) cout << "NO\n";
                flag = false;
            }
            else {
                root->insert(arr);
            }
        }
 
        if (flag) {
            cout << "YES\n";
        }
 
        delete root;
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1707번 - 이분 그래프 (C++)  (0) 2023.06.27
[ 백준 ] 1963번 - 소수 경로 (C++)  (0) 2023.06.26
[ 백준 ] 3649번 - 로봇 프로젝트 (C++)  (0) 2023.06.23
[ 백준 ] 14940번 - 쉬운 최단거리 (C++)  (0) 2023.06.22
[ 백준 ] 17071번 - 숨바꼭질 5 (C++)  (0) 2023.06.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
반응형

 

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

 

14725번: 개미굴

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다.  (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

트라이의 개념을 모른다면 공부하고 이 문제를 푸는 것을 추천합니다!

 

문제의 조건에서 사전 순으로 출력하라고 했으므로 map 자료구조를 이용해서 문제를 풀었습니다. 각각의 노드들은 자식 노드를 가지고 있고, 자식 노드들의 키값은 string입니다. 따라서 map <string, Trie*> map을 만들어 주고 이 노드는 자식 노드의 정보를 포인터의 형식으로 가지고 있습니다.

 

먹이를 벡터로 입력 받아서 만약 해당 깊이에 단어가 존재한다면 그 단어의 자식 노드로 넘어가고, 없다면 단어를 동적 할당을 통해 생성해줍니다. 그러고 나서 자식 노드로 넘어가게 됩니다.

 

이러한 방식으로 모든 입력을 처리하면 map의 특성상 자동으로 오름차순으로 정렬이 되기때문에 따로 정렬해줄 필요 없이 Find 함수를 통해서 출력해주면 됩니다.

 

Find 함수 또한 iiterator를 차례로 순회해주면서 dfs와 비슷한 방식으로 출력해주면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<string>
#include<map>
#include<vector>
 
using namespace std;
 
int N;
 
struct Trie {
    map<string, Trie*> m;        //오름차순으로 출력하기 위해서 map을 씀
    ~Trie() {                    //소멸자로 동적 할당한 Trie들을 delete
        for (auto it = m.begin(); it != m.end(); it++) {
            delete it->second;
        }
    }
 
    void Insert(vector<string> vect, int idx)
    {
        if (vect.size() == idx) return;    //모두 삽입했다면 return
 
        if (m.find(vect[idx]) == m.end()) {    //vect[idx]가 map에 없다면
            m.insert({ vect[idx], new Trie });
        }
 
        m[vect[idx]]->Insert(vect, idx + 1);    //다음 단어를 삽입
    }
 
    void Find(int depth)
    {
        for (auto it = m.begin(); it != m.end(); it++) {
            for (int i = 0; i < depth; i++) {
                printf("--");
            }
            cout << it->first << '\n';
            
            it->second->Find(depth + 1);
        }
    }
};
 
int main()
{
    Trie *root = new Trie();
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int n;
        scanf("%d", &n);
        vector<string> vect(n);
        for (int j = 0; j < n; j++) {
            cin >> vect[j];
        }
 
        root->Insert(vect, 0);
    }
 
    root->Find(0);
    delete root;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
[ 백준 ] 13334번 - 철로 (C++)  (0) 2022.06.29
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25

+ Recent posts

티스토리툴바