반응형

문제 출처 :


https://programmers.co.kr/learn/courses/30/lessons/42577



알고리즘 분석 :


문제 해결에 필요한 사항

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
/*
    https://programmers.co.kr/learn/courses/30/lessons/42577
    트라이를 통해 문제를 해결한다.
*/
 
#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
 
#define MAX_NODE 10
 
using namespace std;
 
struct Trie {
    Trie *next[MAX_NODE];
    bool isEnd;
    bool isVisited;
 
    Trie() {
        for (int i = 0; i < MAX_NODE; i++)
        {
            next[i] = nullptr;
            isEnd = isVisited = false;
        }
    }
    ~Trie() {
        for (int i = 0; i < MAX_NODE; i++)
            if (next[i])
                delete next[i];
    }
};
 
bool solution(vector<string> phone_book) {
    Trie *root = new Trie;
 
    for (int i = 0; i < phone_book.size(); i++) {
        Trie *cur = root;
        int len = phone_book[i].size();
        for (int j = 0; j < len; j++) {
            int nowCh = phone_book[i][j] - '0';
            if (cur->next[nowCh] == nullptr)
                cur->next[nowCh] = new Trie;
 
            // 현재 전화번호보다 짧거나 같은 번호가 여기서 isEnd라면
            // 그 번호는 현재 번호의 접두사이다.
            if (cur->isEnd)
                return false;
 
            // 이미 다른 번호가 여기를 지나갔고 현재 번호의 끝이면
            // 현재 번호는 다른 번호의 접두사이다.
            if (cur->next[nowCh]->isVisited && j == len - 1)
                return false;
 
            cur->next[nowCh]->isVisited = true;
 
            cur = cur->next[nowCh];
        }
        cur->isEnd = true;
    }
 
    return true;
}
cs

반응형