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

C++ 단어 약어 생성 알고리즘: 트라이(Trie)로 충돌 없는 최소 약어 만들기

문제 소개

서로 중복되지 않는 n개의 문자열로 이루어진 배열이 주어졌을 때, 아래 규칙에 따라 모든 단어에 대해 가능한 한 짧은 약어를 생성해야 합니다.

  • 기본 형식: 첫 글자로 시작하고, 생략된 문자의 개수가 이어지며, 마지막 글자로 끝납니다. (예: internationalization → i18n)

  • 충돌 처리: 두 개 이상의 단어가 동일한 약어를 공유하는 경우, 단어→약어 매핑이 고유해질 때까지 첫 글자 하나 대신 더 긴 접두사를 사용합니다.

  • 길이 조건: 약어가 원래 단어보다 짧아지지 않는다면 약어를 만들지 않고 원본 단어를 그대로 유지합니다.

예를 들어 입력이 다음과 같다면,

["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]

출력은 아래와 같습니다.

["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

"like"는 l2e(l + 2글자 생략 + e)로 줄일 수 있지만, "internet", "interval", "intension", "intrusion"처럼 i로 시작하는 단어들은 서로 충돌하기 때문에 접두사를 점점 늘려가며 고유한 약어를 찾아야 합니다. 또한 "god", "me"처럼 길이가 3 이하인 단어는 약어로 줄여도 길이가 같거나 오히려 길어지므로 원본을 그대로 사용합니다.

풀이 접근: 트라이(Trie) 자료구조

이 문제는 트라이(Trie)를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  1. 먼저 모든 단어에 대해 기본 규칙(첫 글자 + 개수 + 마지막 글자)으로 약어를 만듭니다.
  2. 동일한 약어를 가진 단어들을 그룹으로 묶습니다. 충돌이 없는 그룹은 그대로 두면 됩니다.
  3. 충돌이 있는 그룹의 단어들을 트라이에 삽입합니다. 이때 각 노드에는 해당 노드를 지나가는 단어의 수(cnt)를 함께 저장합니다.
  4. 각 단어를 트라이에서 따라가다가 처음으로 cnt가 1이 되는 지점을 찾으면, 그 지점까지의 접두사가 해당 단어만의 고유한 접두사입니다. 이를 이용해 최종 약어를 만듭니다.

알고리즘 상세 단계

1. 노드 구조체 정의 — 각 노드는 지나간 단어 수를 저장하는 cnt와 26개의 자식 포인터 배열(child[26])을 가지며, 처음에는 모두 NULL로 초기화됩니다.

2. freeNode() 함수 — 트라이 전체를 재귀적으로 순회하며 메모리를 해제합니다. head가 NULL이면 즉시 반환하고, 26개 자식 각각에 대해 재귀 호출한 뒤 마지막에 head를 삭제합니다.

3. insertNode() 함수 — 단어 s를 트라이에 삽입합니다. 각 문자 x에 대해 해당 자식 노드가 없으면 새로 생성하고, 그 노드로 이동한 뒤 cnt를 1 증가시킵니다.

4. abbreviate() 함수 — 트라이에서 단어 s를 따라가며 각 노드의 cnt를 확인합니다. 처음으로 cnt가 1인 노드를 만나면 그 위치(i)까지가 고유 접두사입니다. 남은 글자 수 rem = s.size() − (i + 2)를 계산하고, rem이 1 이하이면 원본 s를, 그렇지 않으면 s[0..i] + rem + 마지막 글자를 결과로 반환합니다.

5. wordsAbbreviation() 함수 — 전체 흐름을 제어합니다.

  • 모든 단어에 대해 기본 약어 x를 계산하고, 맵 m[x]에 인덱스를 저장하며 ret[i]에 임시로 저장합니다.
  • m의 각 그룹을 순회하면서, 그룹 크기가 1 이하면(충돌 없음) 건너뜁니다.
  • 충돌 그룹의 단어들을 트라이에 모두 삽입한 뒤, 각 단어에 대해 abbreviate()를 호출해 ret[idx]를 갱신합니다.
  • 작업이 끝나면 freeNode()로 트라이 메모리를 해제하여 누수를 방지합니다.

마지막에 ret 배열을 반환하면 모든 단어의 고유한 최소 약어를 얻을 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}

struct Node{
   int cnt;
   Node* child[26];
   Node(){
      cnt = 0;
      for(int i = 0; i < 26; i++)child[i] = NULL;
   }
};

class Solution {
   public:
   void freeNode(Node* head){
      if (!head)
      return;
      for (int i = 0; i < 26; i++) {
         freeNode(head->child[i]);
      }
      delete head;
   }
   void insertNode(Node* node, string s){
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         if (!node->child[x - 'a']) {
            node->child[x - 'a'] = new Node();
         }
         node = node->child[x - 'a'];
         node->cnt++;
      }
   }
   string abbreviate(Node* node, string s){
      string ret = "";
      Node* curr = node;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         curr = curr->child[x - 'a'];
         if (curr->cnt == 1) {
            int rem = s.size() - (i + 2);
            ret = rem <= 1 ? s : s.substr(0, i + 1) + to_string(rem) + s.back();
            break;
         }
      }
      return ret;
   }
   vector<string> wordsAbbreviation(vector<string>& dict) {
      int n = dict.size();
      vector<string> ret(n);
      map<string, vector<int> > m;
      for (int i = 0; i < n; i++) {
         string word = dict[i];
         int rem = word.size() - 2;
         string x = rem <= 1 ? word : word.front() + to_string(rem) + word.back();
         m[x].push_back(i);
         ret[i] = x;
      }
      Node* head;
      map<string, vector<int> >::iterator it = m.begin();
      while (it != m.end()) {
         if (it->second.size() <= 1) {
            it++;
            continue;
         }
         head = new Node();
         for (int i = 0; i < it->second.size(); i++) {
            int idx = it->second[i];
            insertNode(head, dict[idx]);
         }
         for (int i = 0; i < it->second.size(); i++) {
            int idx = it->second[i];
            ret[idx] = abbreviate(head, dict[idx]);
         }
         freeNode(head);
         it++;
      }
      return ret;
   }
};

main(){
   Solution ob;
   vector<string> v = {"like","god","internal","me","internet","interval","intension","face","intrusion"};
   print_vector(ob.wordsAbbreviation(v));
}

실행 결과

입력

{"like","god","internal","me","internet","interval","intension","face","intrusion"}

출력

[l2e, god, internal, me, i6t, interval, inte4n, f2e, intr4n]

마무리

트라이를 사용하면 충돌하는 단어 그룹 안에서 각 단어가 고유해지는 최소 접두사 길이를 전체 문자 수에 비례하는 시간에 효율적으로 찾을 수 있습니다. 이 패턴은 LeetCode 527번 "Word Abbreviation" 문제와 동일한 유형으로, 문자열 그룹화와 트라이를 결합하는 방식은 접두사 관련 최적화 문제에서 널리 활용되는 강력한 기법입니다.