백준 2800번, 괄호 제거(C, C++)

#include<iostream>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>

using namespace std;

string str;
bool selected[11];
int index_check[201];
stack<int> s;
set<string> same_check;
vector<pair<int, int>> indexstorge;
vector<string> solution;


void DFS(int idx, int cnt){

    if(cnt>= 1){
        string a = "";
        for(int i = 0; i < str.size(); i++){
            if(index_check[i]){
                continue;
            } // 저장된 '(',  ')'을 제외하고 출력하기위해 if문을 사용
            a = a + str[i];
        }

        if(same_check.find(a) == same_check.end()){
            same_check.insert(a);
            solution.push_back(a);
        }

    }

   for(int i = idx; i < indexstorge.size(); i++){
       if(selected[i] == true){
           continue;
       }
       selected[i] = true;
       index_check[indexstorge[i].first] = true;  // 괄호 '('의 인덱스
       index_check[indexstorge[i].second] = true; // 괄호 ')'의 인덱스
       DFS(i, cnt + 1);
       selected[i] = false;
       index_check[indexstorge[i].first] = false;
       index_check[indexstorge[i].second] = false;
   } 
}


int main(){

    cin >> str;

    for(int i = 0; i < str.size(); i++){
        if(str[i] == '('){
            s.push(i); // ( 괄호의 인덱스를 저장
        }else if(str[i] == ')'){
            indexstorge.push_back({s.top(), i}); // 괄호 쌍의 인덱스를 저장.
            s.pop(); 
        }
    }
    DFS(0, 0);

    sort(solution.begin(), solution.end());


    for(int i = 0; i < solution.size(); i++){
        cout << solution[i] <<'\n';
    }

    return 0;
}

조합을 통해서 괄호를 뽑는 경우를 세분화합니다.

(0/(0))가 있다고 생각해봅시다.

1개의 괄호를 제거하는 경우의 수 -> 0/(0) 와 (0/0)이므로 2가지입니다.

2개의 괄호를 제거하는 경우의 수 -> 0/0 1가지입니다.

 

이를 조합의 관점으로 바라보았을 때,  스택 안에 저장된 괄호의 사이즈에서 괄호를 1가지를 뽑는 경우 +

스택 안에 저장된 괄호의 사이즈에서 2가지를 뽑는 경우입니다.

따라서 함수에 if(cnt>=1)으로 설정해준 이유이기도 합니다.

 

 

놓치기 쉬운 부분이 있는데, 결과 값이 중복이 될 수있습니다.

((0))의 경우를 생각해보도록 하겠습니다.

1개의 괄호를 제거하는 경우의 수는 (0), (0)입니다. 바깥 쪽이 제거된건지 안 쪽의 괄호가 제거 된건지는 모르지만 결과 값은 같습니다.

해당 문제에서는 결과 값이 서로 달라야하기 때문에, 중복인 부분은 set함수를 통해 제거하도록 하고

sort정렬을 통해 사전순으로 배치합니다.