C++로 문자열에 공백을 삽입해 만들 수 있는 모든 조합 출력하기

문제 개요

이 문제에서는 하나의 문자열이 주어지며, 문자열의 각 문자 사이에 공백을 삽입해 만들 수 있는 모든 문자열 조합을 출력해야 합니다.

예시를 통해 문제를 더 쉽게 이해해 보겠습니다.

입력: string = 'XYZ'
출력: XYZ, XY Z, X YZ, X Y Z

접근 방법: 재귀 활용

이 문제를 해결하려면 문자열에 공백을 넣을 수 있는 모든 경우의 수를 찾아야 합니다. 이를 위해 재귀(recursion) 기법을 사용합니다. 각 단계마다 두 가지 선택지를 고려합니다.

공백을 넣지 않는 경우: 현재 문자를 버퍼에 그대로 복사한 뒤 다음 문자로 진행합니다.
공백을 넣는 경우: 현재 위치에 공백을 삽입하고 그 뒤에 문자를 복사한 뒤 다음 문자로 진행합니다.

모든 문자를 처리하면 완성된 버퍼를 출력하고, 재귀 호출을 통해 가능한 모든 조합을 빠짐없이 탐색할 수 있습니다.

C++ 구현 예제

#include <iostream>
#include <cstring>
using namespace std;
void printPattern(char str[], char buff[], int i, int j, int n){
    if (i==n){
        buff[j] = '\0';
        cout << buff << endl;
        return;
    }
    buff[j] = str[i];
    printPattern(str, buff, i+1, j+1, n);
    buff[j] = ' ';
    buff[j+1] = str[i];
    printPattern(str, buff, i+1, j+2, n);
}
int main() {
    char *str = "XYZ";
    int n = strlen(str);
    char buf[2*n];
    buf[0] = str[0];
    cout<<"공백으로 생성된 문자열 :\n";
    printPattern(str, buf, 1, 1, n);
    return 0;
}

실행 결과

위 코드를 실행하면 공백을 삽입해 생성할 수 있는 모든 문자열이 출력됩니다.

XYZ
XY Z
X YZ
X Y Z

코드 설명 및 시간 복잡도

printPattern 함수는 두 개의 인덱스를 사용합니다. i는 원본 문자열의 현재 위치를, j는 결과를 저장하는 버퍼의 현재 위치를 가리킵니다. 첫 번째 재귀 호출은 공백 없이 문자를 이어 붙이는 경우를, 두 번째 재귀 호출은 공백을 하나 추가하는 경우를 담당합니다.

길이가 n인 문자열의 경우 문자 사이 공간은 n-1개이며, 각 공간마다 공백을 넣거나 넣지 않는 2가지 선택이 가능하므로 총 2^(n-1)개의 조합이 생성됩니다. 따라서 이 알고리즘의 시간 복잡도는 O(2ⁿ)입니다.