[알고리즘] 문자열 TRIE

문제 정의

• 접두사를 확인하는 문제
  • 접미사도 확인 가능 : 글자를 거꾸로 뒤집으면 됨

문제 접근

• 각 문자열을 TRIE 배열에 저장하면서 문제 해결
  • TRIE 배열
    • 각 문자에 해당하는 노드가 저장되는 곳
    • 노드 포함해야하는 것
      • fin : 이 노드에서 문자열이 끝난적이 있음
      • child : 문자열중 이 노드의 다음 글자의 위치(TRIE 배열 중 인덱스)
• TRIE 배열을 활용해서 문제 해결 가능
  • 접두사가 있는지 확인하는 문제
    • 이미 접두사가 있었는지 확인 : 각 노드의 fin 확인
    • 현재의 문자열이 접두사가 되는경우 : 문자열의 마지막 글자가 이미 있을떄

시간복잡도

• 모든 문자열에 대해 순회 N
• 문자열에 대해 한글자 한글자 순회 : M
• O(NM)

대표예제 : 백준 5052 전화번호 목록

#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;
}