C++에서 문자열을 괄호로 묶어 분할하는 모든 방법 출력하기

이 문제에서는 하나의 문자열이 주어지며, 이를 여러 개의 부분 문자열로 나눈 뒤 각 부분 문자열을 괄호로 묶어 출력해야 합니다.

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

입력 : wxyz
출력 :
    (w) (x) (y) (z)
    (w) (x) (yz)
    (w) (xy) (z)
    (w) (xyz)
    (wx) (y) (z)
    (wx) (yz)
    (wxy) (z)
    (wxyz)

문제 접근 방법

설명 − 주어진 문자열을 가능한 모든 조합으로 부분 문자열로 나누고, 각 부분 문자열을 괄호로 감싸서 출력합니다.

문제를 이해했으니 이제 해결 방법을 만들어 보겠습니다.

여기서는 재귀(recursion)를 활용하여 문제를 해결합니다. 재귀 함수는 두 개의 매개변수를 받는데, 하나는 문자열에서 다음으로 처리할 문자의 인덱스이고, 다른 하나는 지금까지 생성된 출력 문자열입니다. 아직 처리되지 않은 부분 문자열은 재귀 호출이 반복될 때마다 조금씩 처리되며, 그 과정에서 가능한 모든 분할 조합이 만들어집니다.

예제

문제를 해결하는 프로그램은 다음과 같습니다.

#include <iostream>
using namespace std;
void substring(string str, int index, string out){
    if (index == str.length())
        cout << out << endl;
    for (int i = index; i < str.length(); i++)
        substring(str, i + 1, out + "(" + str.substr(index, i+1-index) + ")" );
}
int main(){
    string str = "wxyz";
    cout<<"부분 문자열 목록 :"<<endl;
    substring(str, 0, "");
    return 0;
}

출력 결과

부분 문자열 목록 :
(w)(x)(y)(z)
(w)(x)(yz)
(w)(xy)(z)
(w)(xyz)
(wx)(y)(z)
(wx)(yz)
(wxy)(z)
(wxyz)