문제 정의
- 접두사를 확인하는 문제
- 접미사도 확인 가능 : 글자를 거꾸로 뒤집으면 됨
문제 접근
- 각 문자열을 TRIE 배열에 저장하면서 문제 해결
- TRIE 배열
- 각 문자에 해당하는 노드가 저장되는 곳
- 노드 포함해야하는 것
- fin : 이 노드에서 문자열이 끝난적이 있음
- child : 문자열중 이 노드의 다음 글자의 위치(TRIE 배열 중 인덱스)
- TRIE 배열
- TRIE 배열을 활용해서 문제 해결 가능
- 접두사가 있는지 확인하는 문제
- 이미 접두사가 있었는지 확인 : 각 노드의 fin 확인
- 현재의 문자열이 접두사가 되는경우 : 문자열의 마지막 글자가 이미 있을떄
- 접두사가 있는지 확인하는 문제
시간복잡도
- 모든 문자열에 대해 순회 N
- 문자열에 대해 한글자 한글자 순회 : M
- O(NM)
대표예제 : 백준 5052 전화번호 목록
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 | #include <iostream> #include <string> #include <vector> using namespace std; // 각 문자가 들어갈 node 정의 struct node { // 문자열이 끝날경우 fin = true; bool fin; // 다음 문자의 위치(TRIE 안에서의 인덱스) // 현재 문제는 숫자이므로 10개만, 알파벳이면 26개 int child[10]; // 초기화 node() { fin = false; // child값이 -1일 경우, 다음 글자가 없음 for(int i=0; i<10; i++) child[i] = -1; } }; vector<node> trie; bool sw; // s : trie에 넣을 문자열 // idx : 문자열중 현재 글자의 위치 (인덱스) // nodi : 삽입할 노드의 인덱스, 처음 시작은 0부터 시작 void insert(string& s, int idx, int nodi) { if(idx==s.size()) { // 마지막 글자일경우 trie[nodi].fin = true; return; } // 현재 노드에서의 글자 int cur = s[idx] -'0'; // 이미 접두사가 있을경우 if(trie[nodi].fin == true) sw = 1; // 내가 접두사가 될경우, 문자열의 마지막 글자인 동시에 trie에는 다음 글자가 있을때 if(idx == s.size()-1 && trie[nodi].child[cur] != -1) sw = 1; // 문자열의 다음 글자가 없을경우 노드 추가 if(trie[nodi].child[cur] == -1) { trie[nodi].child[cur] = trie.size(); trie.push_back(node()); } // 다음 글자를 TRIE에 삽입 insert(s,idx+1,trie[nodi].child[cur]); } int main() { int t; cin >> t; while(t--) { sw =false; trie.clear(); // TRIE 배열에 처음 시작하는 빈 노드를 넣어줘야함 trie.push_back(node()); int N; cin >> N; while(N--) { string s; cin >> s; // 각 문자열을 trie에 삽입 insert(s,0,0); } if(sw) cout << "NO\n"; else cout << "YES\n"; } return 0; } | cs |
'알고리즘 > 개념' 카테고리의 다른 글
[알고리즘] Dijkstra, 다익스트라 알고리즘 (0) | 2021.02.14 |
---|---|
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘 (0) | 2021.02.08 |
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리 (0) | 2021.02.08 |
[알고리즘] 문자열 KMP, Rabin Karp (0) | 2021.02.07 |
[알고리즘] Topological Sort, 위상정렬 (0) | 2021.02.07 |