이번 글에서는 주어진 문자열의 영숫자 약어(alphanumeric abbreviation)와 관련된 흥미로운 문제를 살펴보겠습니다. 문자열의 길이는 10 미만이라고 가정하며, 생성 가능한 모든 영숫자 약어를 출력하는 것이 목표입니다.
영숫자 약어란 문자와 숫자가 섞여 있는 형태를 말합니다. 이때 숫자의 값은 해당 위치에서 생략(건너뛴)된 문자의 개수를 의미합니다. 생략되는 부분 문자열은 여러 곳에 존재할 수 있지만, 두 생략 구간이 서로 인접할 수는 없습니다. 인접하게 되면 하나의 더 큰 숫자로 합쳐져야 하기 때문입니다. 그럼 문제를 해결하기 위한 알고리즘부터 알아보겠습니다.
알고리즘
핵심 아이디어는 재귀 호출과 백트래킹을 활용하는 것입니다. 문자열의 각 위치에서 두 가지 선택지 중 하나를 고릅니다.
- 현재 문자를 결과 문자열에 그대로 추가하고 다음 인덱스로 진행한다.
- 현재 문자를 건너뛰고, 지금까지 연속으로 생략한 문자 수를 뜻하는 숫자를 결과에 추가한다. 단, 결과 문자열의 마지막 문자가 이미 숫자라면 그 값에 1을 더해 갱신함으로써 두 생략 구간이 인접하지 않도록 한다.
이를 의사 코드로 표현하면 다음과 같습니다.
printAbbreviation(s, index, max, str) −
begin
if index == max, then // 문자열 끝에 도달한 경우
print str // 완성된 약어 출력
end if
add s[index] to str // 현재 문자를 결과에 추가 (선택지 1)
printAbbreviation(s, index + 1, max, str)
delete last character from str
count := 1
if str is not empty, then
if last character of str is a digit, then // 마지막이 숫자면
add last digit with the count value // 기존 숫자에 1을 누적
delete last character from str // (선택지 2)
end if
end if
add count after the str // 생략 개수를 숫자로 추가
printAbbreviation(s, index + 1, max, str)
endC++ 구현 예제
다음은 위 알고리즘을 C++로 구현한 전체 코드입니다. 입력 문자열 "HELLO"에 대해 가능한 모든 약어 조합을 출력합니다.
#include <iostream>
using namespace std;
void printAbbreviation(const string& s, int index, int max_index, string str) {
if (index == max_index) { // 문자열을 끝까지 처리한 경우
cout << str << endl;
return;
}
str.push_back(s[index]); // 현재 문자를 결과에 추가
printAbbreviation(s, index + 1, max_index, str); // 다음 인덱스부터 재귀 호출
str.pop_back(); // 마지막 문자 제거 (백트래킹)
int count = 1;
if (!str.empty()) {
if (isdigit(str.back())) { // 마지막 문자가 숫자라면
count += (int)(str.back() - '0'); // 해당 숫자 값을 count에 누적
str.pop_back(); // 마지막 문자 제거
}
}
char to_char = (char)(count + '0'); // count를 문자로 변환
str.push_back(to_char); // 생략 개수를 숫자로 추가
printAbbreviation(s, index + 1, max_index, str); // 다음 인덱스 처리
}
void printCombination(string str) {
if (!str.length()) // 빈 문자열이면 종료
return;
string str_res;
printAbbreviation(str, 0, str.length(), str_res);
}
int main() {
string str = "HELLO";
printCombination(str);
}실행 결과
길이가 5인 문자열 "HELLO"의 각 자리는 '문자 유지' 또는 '생략' 두 가지 상태를 가질 수 있으므로, 총 25 = 32개의 조합이 출력됩니다.
HELLO HELL1 HEL1O HEL2 HE1LO HE1L1 HE2O HE3 H1LLO H1LL1 H1L1O H1L2 H2LO H2L1 H3O H4 1ELLO 1ELL1 1EL1O 1EL2 1E1LO 1E1L1 1E2O 1E3 2LLO 2LL1 2L1O 2L2 3LO 3L1 4O 5
정리 및 참고 사항
이 알고리즘은 각 문자를 '유지'할지 '생략'할지 결정하며 재귀적으로 모든 경우를 탐색합니다. 시간 복잡도는 문자열 길이를 n이라 할 때 O(2ⁿ)이며, 생성되는 약어의 개수 역시 최대 2ⁿ개입니다.
한 가지 유의할 점은 숫자 카운트가 한 자리 숫자(1~9)만 표현할 수 있다는 것입니다. 이것이 입력 문자열의 길이가 10 미만이라는 제약 조건을 두는 이유입니다. 만약 더 긴 문자열을 다루려면, 연속된 생략 개수가 10 이상일 때 숫자를 여러 자리로 변환하는 로직을 추가해야 합니다.