C++로 두 문자열의 모든 인터리빙 문자열 출력하기

문제 개요

이 문제에서는 두 개의 문자열 str1과 str2가 주어지며, 두 문자열을 섞어 만들 수 있는 모든 인터리빙(interleaving) 문자열을 출력해야 합니다.

인터리빙 문자열이란 주어진 두 문자열의 모든 문자를 사용하되, 각 문자열 내부에서 문자들의 상대적인 순서는 그대로 유지되는 문자열을 의미합니다.

예제를 통해 문제를 자세히 살펴보겠습니다.

입력: str1 = "XY", str2 = "NS"
출력: XYNS, XNYS, XNSY, NXYS, NXSY, NSXY

접근 방법

이 문제를 해결하려면 두 문자열에 포함된 모든 문자를 활용해야 합니다. str1의 길이를 m, str2의 길이를 n이라고 할 때, 생성할 수 있는 인터리빙 문자열의 총 개수는 조합 공식에 따라 C(m+n, m)개입니다.

모든 인터리빙 문자열을 출력하기 위해서는 한 번에 한 문자씩 선택하여 결과 문자열에 배치한 뒤, 남은 문자들에 대해 재귀적으로 함수를 호출하는 방식을 사용합니다. 즉, 다음 문자를 str1에서 가져오는 경우와 str2에서 가져오는 경우를 모두 탐색하면 가능한 모든 조합을 얻을 수 있습니다.

구현 예제

위에서 설명한 로직의 구현 코드는 다음과 같습니다.

#include <iostream>
#include <string.h>
using namespace std;
void printStrings (char *str1, char *str2, char *iStr, int m, int n, int i) {
    if (m == 0 && n == 0)
        cout<<iStr<<endl ;
    if (m != 0) {
        iStr[i] = str1[0];
        printStrings(str1 + 1, str2, iStr, m - 1, n, i + 1);
    }
    if (n != 0) {
        iStr[i] = str2[0];
        printStrings(str1, str2 + 1, iStr, m, n - 1, i + 1);
    }
}
void generateInterleavingString(char *str1, char *str2, int m, int n) {
    char *iStr= new char[((m + n + 1)*sizeof(char))];
    iStr[m + n] ='\0';
    printStrings(str1, str2, iStr, m, n, 0);
}
int main() {
    char str1[] = "XY";
    char str2[] = "NS";
    cout<<"All interleaving string are :\n";
    generateInterleavingString(str1, str2, strlen(str1), strlen(str2));
    return 0;
}

실행 결과

All interleaving string is −
XYNS
XNYS
XNSY
NXYS
NXSY
NSXY

동작 원리 및 복잡도 분석

핵심 함수인 printStrings는 두 문자열에서 아직 사용하지 않은 문자의 개수(m, n)를 추적합니다. 두 값이 모두 0이 되면 결과 문자열 iStr이 완성된 것이므로 이를 출력합니다. m이 0이 아니면 str1의 첫 번째 문자를 현재 위치에 배치하고 재귀 호출을 진행하며, n이 0이 아니면 str2의 첫 번째 문자를 배치하는 경우도 마찬가지로 탐색합니다.

이 알고리즘의 시간 복잡도는 O(2^(m+n))이며, 각 재귀 단계마다 두 가지 선택지(str1에서 가져오기 또는 str2에서 가져오기)가 존재하기 때문입니다. 입력 문자열의 길이가 길어질수록 결과의 개수가 기하급수적으로 증가하므로, 이 방법은 비교적 짧은 문자열에 적합합니다.