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

C++로 단어의 최단 인코딩 구현하기 – 트라이(Trie) 활용 방법

문제 소개

단어 목록이 주어지면, 참조 문자열(reference string) S와 인덱스 리스트 A를 작성하여 이를 인코딩할 수 있습니다. 예를 들어 단어 목록이 ["time", "me", "bell"]이라면, S = "time#bell#"이고 indexes = [0, 2, 5]로 표현할 수 있습니다. 각 인덱스 위치에서는 참조 문자열을 해당 지점부터 "#" 기호를 만날 때까지 읽어 원래 단어를 복원합니다.

따라서 우리가 구해야 하는 것은 주어진 단어들을 모두 인코딩할 수 있는 가장 짧은 참조 문자열 S의 길이입니다. 위 예제에서 정답은 10입니다.

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

이 문제는 트라이(Trie) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 단어들을 길이 기준으로 내림차순 정렬합니다.
  • 각 단어를 뒤에서부터(역순으로) 트라이에 삽입합니다.
  • 삽입 과정에서 새로운 노드가 생성되었다면, 그 단어는 다른 단어의 접미사가 아니므로 인코딩 길이에 포함해야 합니다.
  • 새 노드가 하나도 생성되지 않았다면, 해당 단어는 이미 삽입된 더 긴 단어의 접미사이므로 별도로 인코딩할 필요가 없습니다.

길이가 긴 단어를 먼저 처리하면, 접미사 관계에 있는 짧은 단어들이 자동으로 걸러지기 때문에 최적의 결과를 얻을 수 있습니다. 또한 각 단어 뒤에는 반드시 "#" 구분 기호가 붙으므로, 유효한 단어마다 길이에 1을 더해주어야 합니다.

알고리즘 단계

  1. insertNode 메서드를 정의합니다. 이 메서드는 head 노드와 문자열 s를 매개변수로 받습니다.
  2. curr := head, flag := false로 초기화합니다.
  3. i를 s.size() - 1부터 0까지 감소시키며 반복합니다.
    • x := s[i]
    • curr의 m[x]가 null이면 flag := true로 설정하고 새 노드를 생성하여 curr의 m[x]에 저장합니다.
    • curr := curr의 m[x]로 갱신합니다.
  4. flag가 true이면 s의 크기를 반환하고, 그렇지 않으면 0을 반환합니다.
  5. 메인 메서드에서는 다음을 수행합니다.
  6. ret := 0, head := 새 노드로 초기화합니다.
  7. words 배열을 길이 기준으로 내림차순 정렬합니다.
  8. n := words의 크기
  9. i를 0부터 n-1까지 반복합니다.
    • temp := insertNode(head, words[i])
    • temp가 0이 아니면 ret := ret + temp + 1
  10. ret을 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
struct Node{
    map <char, Node*> m;
};
class Solution {
    public:
    static bool cmp(string a, string b){
        return a.size() > b.size();
    }
    int insertNode(Node* head, string s){
        Node* curr = head;
        bool flag = false;
        for(int i = s.size() - 1; i >= 0; i--){
            char x = s[i];
            if(!curr->m[x]){
                flag = true;
                curr->m[x] = new Node();
            }
            curr = curr->m[x];
        }
        return flag? (int)s.size() : 0;
    }
    int minimumLengthEncoding(vector<string>& words) {
        int ret = 0;
        Node* head = new Node();
        sort(words.begin(), words.end(), cmp);
        int n = words.size();
        for(int i = 0; i < n; i++){
            int temp= insertNode(head, words[i]);
            if(temp){
                ret += (temp + 1);
            }
        }
        return ret;
    }
};
main(){
    vector<string> v = {"time", "me", "bell"};
    Solution ob;
    cout << (ob.minimumLengthEncoding(v));
}

실행 결과

입력:

["time", "me", "bell"]

출력:

10

복잡도 분석

시간 복잡도는 단어 정렬에 O(N log N · L)(N은 단어 개수, L은 평균 단어 길이), 트라이 삽입에는 전체 문자 수에 비례하는 O(ΣL)이 소요되므로 전체적으로 O(N log N · L + ΣL)입니다. 공간 복잡도는 트라이에 저장되는 노드 수에 비례하여 O(ΣL)입니다.