문제 소개
문자열 S가 하나의 단어 목록을 나타낸다고 가정해 보겠습니다. 이때 단어를 구성하는 각 문자는 하나 이상의 옵션을 가질 수 있습니다. 옵션이 하나뿐이라면 해당 문자는 그대로 표현되고, 옵션이 여러 개라면 중괄호({})로 감싸서 표현합니다.
예를 들어 "{a,b,c}"는 옵션 ["a", "b", "c"]를 의미합니다. 따라서 입력이 "{a,b,c}d{e,f}"와 같다면, 이 문자열은 다음 목록을 나타냅니다.
["ade", "adf", "bde", "bdf", "cde", "cdf"]
즉, 이 방식으로 만들 수 있는 모든 단어를 사전순(lexicographical order)으로 반환하는 것이 문제의 목표입니다.
해결 전략: 백트래킹(DFS)
이 문제는 재귀적 탐색, 즉 백트래킹 기법으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 입력 문자열을 먼저 파싱하여 각 위치별로 선택 가능한 문자 그룹을 분리한 뒤, 각 그룹에서 문자를 하나씩 선택하면서 재귀적으로 조합을 완성하는 것입니다.
알고리즘 단계
- 결과를 저장할 배열
ret과 정수형 변수n을 정의합니다. solve()메서드를 정의합니다. 이 메서드는 인덱스(index), 문자 그룹 리스트(list), 현재까지 만든 문자열(curr)을 입력으로 받습니다.index == n이면 모든 그룹을 순회한 것이므로curr를ret에 추가하고 종료합니다.- 그렇지 않으면
i를 0부터list[index]의 크기까지 반복하며solve(index + 1, list, curr + list[index][i])를 재귀 호출합니다.
메인 로직: 입력 문자열 파싱
- 크기 100의 문자열 벡터를 생성하고,
n := 0,flag := false로 초기화합니다. - 문자열
s를 처음부터 끝까지 순회하며 다음을 수행합니다.- 문자가 쉼표(
,)라면 건너뜁니다. - 여는 중괄호(
{)라면flag := true로 설정합니다. - 닫는 중괄호(
})라면flag := false로 설정하고n을 1 증가시킵니다. - 일반 문자라면
list[n]에 해당 문자를 추가하고,flag가 false라면(단일 옵션인 경우)n을 1 증가시킵니다.
- 문자가 쉼표(
solve(0, list, 빈 문자열)을 호출하여 모든 조합을 생성합니다.ret배열을 오름차순으로 정렬한 뒤 반환합니다.
정렬 단계가 마지막에 포함되므로, 생성된 단어의 개수를 K라고 할 때 전체 시간 복잡도는 O(K log K)에 지배됩니다.
C++ 구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector <string> ret;
int n;
vector<string> expand(string s) {
vector <string> list(100);
n = 0;
int flag = false;
for(int i = 0; i < s.size(); i++){
if(s[i] == ','){
continue;
}else if(s[i] == '{'){
flag = true;
}else if(s[i] == '}'){
flag = false;
n++;
}else{
list[n] += s[i];
if(!flag)n++;
}
}
solve(0, list);
sort(ret.begin(), ret.end());
return ret;
}
void solve(int idx, vector <string> list, string curr = ""){
if(idx == n){
ret.push_back(curr);
return;
}
for(int i = 0; i < list[idx].size(); i++){
solve(idx + 1, list, curr + list[idx][i]);
}
}
};
main(){
Solution ob;
print_vector(ob.expand("{a,b}c{d,e}f"));
}입력
"{a,b}c{d,e}f"출력
[acdf, acef, bcdf, bcef]
위 예제에서 첫 번째 그룹 {a,b}, 두 번째 그룹 {d,e}의 모든 조합이 사이의 고정 문자 c와 f를 포함하여 생성되고, 최종적으로 사전순으로 정렬되어 출력됩니다.