C++ 트라이(Trie)를 활용해 두 사전 단어의 연결로 단어 형성하기

문제 개요

이 문제에서는 하나의 사전(dictionary)과 하나의 단어(word)가 주어지며, 주어진 단어가 사전에 있는 두 단어를 이어 붙여서 만들 수 있는지 확인해야 합니다.

단, 단어를 조합할 때 같은 단어를 반복해서 사용하는 것은 허용되지 않습니다.

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

입력

dictionary = {"hello", "tutorials", "program", "problem", "coding", "point"}
word = "tutorialspoint"

출력

yes

설명

"tutorialspoint"는 사전의 "tutorials"와 "point"를 연결하여 만들 수 있습니다.

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

이 문제는 트라이(trie), 즉 접두사 트리(prefix tree)라고도 불리는 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 전체적인 해결 과정은 다음과 같습니다.

1. 사전의 모든 단어를 트라이에 삽입합니다.
2. 주어진 단어를 앞에서부터 탐색하며, 트라이 안에서 완전한 단어로 끝나는 가장 긴 접두사를 찾습니다.
3. 해당 지점을 기준으로 단어를 두 부분으로 나눈 뒤, 나머지 부분 역시 트라이에서 완전한 단어인지 검색합니다.
4. 두 부분이 모두 사전에 존재하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

C++ 구현 코드

#include<bits/stdc++.h>
using namespace std;
#define char_int(c) ((int)c - (int)'a')
#define SIZE (26)
struct TrieNode{
    TrieNode *children[26];
    bool isLeaf;
};
TrieNode *getNode(){
    TrieNode *newNode = new TrieNode;
    newNode->isLeaf = false;
    for (int i = 0; i < 26; i++)
        newNode->children[i] = NULL;
    return newNode;
}
void insert(TrieNode *root, string Key){
    int n = Key.length();
    TrieNode *pCrawl = root;
    for (int i = 0; i < n; i++){
        int index = char_int(Key[i]);
        if (pCrawl->children[index] == NULL)
            pCrawl->children[index] = getNode();
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isLeaf = true;
}
int prefixSearch(struct TrieNode *root, string key){
    int pos = -1, level;
    struct TrieNode *pCrawl = root;
    for (level = 0; level < key.length(); level++){
        int index = char_int(key[level]);
        if (pCrawl->isLeaf == true)
            pos = level;
        if (!pCrawl->children[index])
            return pos;
        pCrawl = pCrawl->children[index];
    }
    if (pCrawl != NULL && pCrawl->isLeaf)
        return level;
}
bool isWordCreated(struct TrieNode* root, string word){
    int len = prefixSearch(root, word);
    if (len == -1)
        return false;
    string split_word(word, len, word.length() - len);
    int split_len = prefixSearch(root, split_word);
    return (len + split_len == word.length());
}
int main() {
    vector<string> dictionary = {"tutorials", "program", "solving", "point"};
    string word = "tutorialspoint";
    TrieNode *root = getNode();
    for (int i = 0; i < dictionary.size(); i++)
        insert(root, dictionary[i]);
    cout << "Word formation using dictionary is ";
    isWordCreated(root, word) ? cout << "possible" : cout << "not possible";
    return 0;
}

실행 결과

Word formation using dictionary is possible

주어진 단어 "tutorialspoint"는 "tutorials"와 "point"의 연결로 만들 수 있으므로 "possible"이 출력됩니다.

시간 복잡도

사전에 포함된 단어의 개수를 N, 각 단어의 최대 길이를 L이라고 하면, 트라이를 구축하는 데 O(N×L)의 시간이 걸리며, 단어 형성 가능 여부를 확인하는 데는 O(L)의 시간이 소요됩니다.