C++로 주어진 단어 목록의 최단 고유 접두사 찾기

이 문제에서는 단어 배열 arr[]가 주어지며, 목록에 포함된 모든 단어에 대해 가장 짧은 고유 접두사를 찾아내는 것이 과제입니다.

문제를 이해하기 위해 예시를 살펴보겠습니다.

입력

arr[] = {"learn", "programming", "code"}

출력

c leap lear p

출력 결과를 보면 "learn"에는 "lear", "programming"에는 "p", "code"에는 "c"가 각각 대응되며, 이 접두사들은 다른 어떤 단어와도 겹치지 않는 유일한 값입니다.

해결 접근 방식

가장 단순한 해결 방법은 각 단어의 모든 접두사를 하나씩 생성한 뒤, 해당 접두사가 배열 내 다른 단어들의 접두사와 일치하는지 검사하는 것입니다. 일치하지 않는 접두사가 발견되면 그것을 결과로 출력하면 됩니다. 하지만 이 방법은 시간 복잡도가 높아 단어 수가 많아질수록 비효율적입니다.

더 효율적인 접근 방식은 트라이(Trie) 자료 구조를 활용하는 것입니다. 먼저 트라이를 구성하여 모든 단어를 저장하고, 삽입 과정에서 각 노드를 방문하는 빈도(freq)를 기록합니다. 이후 각 단어에 대해 루트 노드부터 해당 단어까지의 경로, 즉 접두사를 추적할 때 방문 빈도가 1인 노드를 만나는 지점이 곧 최단 고유 접두사가 됩니다. 따라서 빈도가 1인 노드부터 시작하는 경로들을 모두 출력하면 원하는 결과를 얻을 수 있습니다.

솔루션의 동작을 보여주는 프로그램입니다.

예시

#include<iostream>
using namespace std;
#define MAX 256
struct trieNode {
    struct trieNode *child[MAX];
    int freq;
};
struct trieNode *newTrieNode(void){
    struct trieNode *newNode = new trieNode;
    newNode->freq = 1;
    for (int i = 0; i<MAX; i++)
        newNode->child[i] = NULL;
    return newNode;
}
void insert(struct trieNode *root, string str) {
    int len = str.length();
    struct trieNode *pCrawl = root;
    for (int level = 0; level<len; level++) {
        int index = str[level];
        if (!pCrawl->child[index])
            pCrawl->child[index] = newTrieNode();
        else
            (pCrawl->child[index]->freq)++;
        pCrawl = pCrawl->child[index];
    }
}
void findShortestUniquePrefixRec(struct trieNode *root, char prefixChar[], int ind) {
    if (root == NULL)
        return;
    if (root->freq == 1) {
        prefixChar[ind] = '\0';
        cout<<prefixChar<<endl;
        return;
    }
    for (int i=0; i<MAX; i++) {
        if (root->child[i] != NULL) {
            prefixChar[ind] = i;
            findShortestUniquePrefixRec(root->child[i], prefixChar, ind+1);
        }
    }
}
void findShortestUniquePrefix(string arr[], int n) {
    struct trieNode *root = newTrieNode();
    root->freq = 0;
    for (int i = 0; i<n; i++)
        insert(root, arr[i]);
    char prefixChar[250];
    findShortestUniquePrefixRec(root, prefixChar, 0);
}
int main() {
    string arr[] = {"learn", "programming", "code", "leap"};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"All Shortest unique prefix for every words in a given list are : \n";
    findShortestUniquePrefix(arr, n);
    return 0;
}

출력

All Shortest unique prefix for every words in a given list are −
c
leap
lear
p