C++로 구현하는 일반화된 약어(Generalized Abbreviation) 생성 알고리즘

문제 소개

하나의 단어가 주어졌을 때, 그 단어의 일반화된 약어(generalized abbreviation)를 모두 생성하는 함수를 작성해야 합니다. 일반화된 약어란 단어 내 연속된 문자 일부를 그 개수에 해당하는 숫자로 대체한 형태를 의미하며, 인접한 두 숫자가 서로 붙어 있어서는 안 됩니다.

예를 들어 입력이 "word"라면 출력은 ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]가 됩니다.

해결 접근 방법

이 문제는 백트래킹(backtracking) 기법으로 효율적으로 해결할 수 있습니다. 각 문자 위치에서 '문자를 그대로 유지'하거나 '숫자로 대체'하는 두 가지 선택지를 재귀적으로 탐색하고, 바로 앞 위치가 이미 숫자인 경우에는 그 값을 1씩 증가시키는 방식으로 처리합니다. 구체적인 단계는 다음과 같습니다.

결과를 저장할 배열 ret을 선언합니다.
문자열 s와 인덱스 idx를 매개변수로 받는 solve() 함수를 정의합니다.
idx가 s의 길이 이상이면 s를 ret의 끝에 추가하고 함수를 종료합니다.
y := s의 인덱스 0부터 idx-1까지의 부분 문자열
i := y의 마지막 인덱스(y.size() - 1)
num := 빈 문자열
i가 0 이상이고 y[i]가 숫자('0'~'9')인 동안 다음을 반복합니다.
- num := y[i] + num (앞쪽에 문자를 덧붙임)
- i를 1만큼 감소
i가 y.size() - 1과 같지 않다면, 즉 바로 앞에 숫자가 존재한다면:
- ret := s의 앞부분(idx - (y.size() - 1 - i)까지) + (num + 1)의 문자열 + s의 뒷부분(idx + 1부터)을 연결한 새 문자열
- s1 := (num + 1)의 문자열 표현, s2 := num의 문자열 표현
- s1과 s2의 길이가 같으면(자릿수 변화 없음) solve(ret, idx) 호출
- 길이가 다르면(자릿수가 증가함) solve(ret, idx + 1) 호출
그렇지 않은 경우(바로 앞이 숫자가 아닌 경우):
- prev := s[idx] 값을 임시 저장
- s[idx] := '1'로 변경한 뒤 solve(s, idx + 1) 호출
- s[idx] := prev로 복원하여 상태를 되돌림(백트래킹)
마지막으로 현재 문자를 그대로 유지하는 경우도 탐색하기 위해 solve(s, idx + 1) 호출

메인 함수에서는 solve(word, 0)을 호출한 뒤 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;
}
class Solution {
public:
   vector<string> ret;
   void solve(string s, int idx){
      if (idx >= s.size()) {
         ret.push_back(s);
         return;
      }
      string y = s.substr(0, idx);
      int i = y.size() - 1;
      string num = "";
      while (i >= 0 && y[i] <= '9' && y[i] >= '0') {
         num = y[i] + num;
         i--;
      }
      if (i != y.size() - 1) {
         string ret = s.substr(0, idx - (y.size() - 1 - i)) + to_string(stoi(num) + 1) + s.substr(idx + 1);
         string s1 = to_string(stoi(num) + 1);
         string s2 = to_string(stoi(num));
         if (s1.size() == s2.size())
            solve(ret, idx);
         else
            solve(ret, idx + 1);
      }
      else {
         char prev = s[idx];
         s[idx] = '1';
         solve(s, idx + 1);
         s[idx] = prev;
      }
      solve(s, idx + 1);
   }
   vector<string> generateAbbreviations(string word){
      solve(word, 0);
      return ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.generateAbbreviations("hello"));
}

실행 결과 확인

입력

hello

출력

[5, 4o, 3l1, 3lo, 2l2, 2l1o, 2ll1, 2llo, 1e3, 1e2o, 1e1l1, 1e1lo, 1el2, 1el1o, 1ell1, 1ello, h4, h3o, h2l1, h2lo, h1l2, h1l1o, h1ll1, h1llo, he3, he2o, he1l1, he1lo, hel2, hel1o, hell1, hello]

복잡도 분석

단어의 각 문자마다 '유지' 또는 '숫자로 대체'라는 두 가지 선택이 가능하므로, 생성되는 약어의 총 개수는 최대 2^n개입니다. 따라서 이 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(2^n)이며, n은 단어의 길이입니다.