Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 트라이(Trie)로 문자 배열로 만들 수 있는 모든 유효한 단어 출력하기

문제 개요

이 문제에서는 하나의 단어 집합과 문자 배열이 주어지며, 배열에 포함된 글자들만 사용해 만들 수 있는 단어들을 찾아 출력해야 합니다.

예시를 통해 문제를 더 자세히 살펴보겠습니다.

입력 :
words[] = {'go', 'hi', 'run', 'on', 'hog', 'gone'}
char[] = {'a', 'o', 'h', 'g'}

출력 : go, hog

설명 − 주어진 단어 중 go와 hog는 문자 배열 {'a', 'o', 'h', 'g'}에 있는 글자들만으로 구성되어 있으므로 유효한 단어입니다. 반면 hi, run, on, gone은 배열에 없는 문자(i, r, u, n, e)를 포함하고 있기 때문에 제외됩니다.

접근 방법: 트라이(Trie) 활용

이 문제는 트라이(Trie) 자료구조를 이용하면 효율적으로 해결할 수 있습니다. 트라이는 문자열 검색에 최적화된 트리 구조로, 공통 접두사를 공유하는 단어들을 효과적으로 저장하고 탐색할 수 있습니다.

전체적인 알고리즘의 동작 과정은 다음과 같습니다.

  1. 주어진 모든 단어를 트라이에 삽입합니다.
  2. 문자 배열의 각 글자에 대해 크기 26의 불리언 배열(해시)을 만들어 해당 알파벳의 존재 여부를 표시합니다.
  3. 트라이를 루트부터 탐색하되, 해시에 표시된 글자이면서 동시에 트라이에 해당 자식 노드가 존재하는 경우에만 탐색을 계속 진행합니다.
  4. 탐색 도중 리프(leaf) 노드에 도달하면, 지금까지 경로를 따라 만든 문자열이 배열의 글자들로 구성된 유효한 단어이므로 이를 출력합니다.

이 방식은 배열에 없는 문자로 연결되는 가지를 아예 탐색하지 않으므로, 모든 단어를 일일이 대조하는 것보다 훨씬 효율적입니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
#define char_int(c) ((int)c - (int)'a')
#define int_to_char(c) ((char)c + (char)'a')
struct TrieNode{
    TrieNode *Child[26];
    bool leaf;
};
TrieNode *getNode(){
    TrieNode * newNode = new TrieNode;
    newNode->leaf = false;
    for (int i =0 ; i< 26 ; i++)
       newNode->Child[i] = NULL;
    return newNode;
}
void insertnode(TrieNode *root, char *Key){
    int n = strlen(Key);
    TrieNode * pChild = root;
    for (int i=0; i<n; i++){
       int index = char_int(Key[i]);
       if (pChild->Child[index] == NULL)
          pChild->Child[index] = getNode();
       pChild = pChild->Child[index];
    }
    pChild->leaf = true;
}
void vaidword(TrieNode *root, bool Hash[], string str){
    if (root->leaf == true)
       cout << str << "\t" ;
    for (int K =0; K < 26; K++){
       if (Hash[K] == true && root->Child[K] != NULL ){
          char c = int_to_char(K);
          vaidword(root->Child[K], Hash, str + c);
       }
    }
}
void PrintAllWords(char Arr[], TrieNode *root, int n){
    bool Hash[26];
    for (int i = 0 ; i < n; i++)
    Hash[char_int(Arr[i])] = true;
    TrieNode *pChild = root ;
    string str = "";
    for (int i = 0 ; i < 26 ; i++){
       if (Hash[i] == true && pChild->Child[i] ){
          str = str+(char)int_to_char(i);
          vaidword(pChild->Child[i], Hash, str);
          str = "";
       }
    }
}
int main(){
    char Dict[][20] = {"go" , "hi" , "run" , "on" , "hog" , "gone"} ;
    TrieNode *root = getNode();
    int n = sizeof(Dict)/sizeof(Dict[0]);
    for (int i=0; i<n; i++)
       insertnode(root, Dict[i]);
    char arr[] = {'a', 'o', 'g', 'h'} ;
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"The words which are valid\t";
    PrintAllWords(arr, root, N);
    return 0;
}

출력 결과

The words which are valid go hog

코드 설명 및 복잡도 분석

  • insertnode(): 한 단어를 트라이에 삽입합니다. 각 문자를 인덱스로 변환해 자식 노드를 순차적으로 생성하며, 단어의 끝에서 리프 플래그를 true로 설정합니다.
  • vaidword(): 현재 노드가 리프 노드라면 지금까지 누적한 문자열을 출력하고, 해시에 허용된 글자 중 자식 노드가 존재하는 경우에만 재귀적으로 탐색을 이어갑니다.
  • PrintAllWords(): 문자 배열을 기반으로 해시 배열을 초기화한 뒤, 유효한 시작 글자부터 깊이 우선 탐색을 시작합니다.

시간 복잡도 − 트라이 구축에는 전체 단어 길이의 합에 비례하는 O(N×L)이 소요되며(N은 단어 개수, L은 평균 단어 길이), 탐색은 배열 글자로 연결되는 경로만 방문하므로 매우 효율적입니다. 공간 복잡도 − 트라이 노드 저장에 O(26×N×L)의 메모리가 필요합니다.