백준 - 2800 괄호 제거

[문제 링크]

짝 괄호를 지우는 모든 경우의 수를 구하는 문제이다.

처음엔 반복문으로 시도하고자 했으나 총 경우의 수인 2^(괄호 짝의 갯수)를 반복문으로 어떻게 표현할지 감이 오질않아서.

재귀로 해결하였다.

먼저 문자열을 한번 순회하며 스택을 이용해 짝괄호의 인덱스를 저장한다.

이렇게 저장한 인덱스들을 이용해서 문자열을 하나하나 완성해 나가면 된다.

문자열을 만들어 나가는데 가능한 경우의 수는 다음과 같다.

 가능한 경우의 수

 1. 현재 문자가 괄호일경우 : (1) 괄호를 지운다, (2) 괄호를 지우지 않는다.

 2. 현재 문자가 괄호가 아닐 경우 : 문자를 붙이고 문자열을 만들어간다.

여는 괄호가 나왔을 때, 짝 괄호에 괄호를 지웠다고 체크하고, 문자열을 이어 붙인다.

그와 대응되는 짝 괄호가 나타나면 그 괄호는 문자열에 포함시키지 않으면 된다.

완성된 문자열은 set에 저장하고, 모든 괄호를 지우지 않을 경우만 set에서 제거한 뒤에 출력하면 된다.

#include <iostream>
#include <string>
#include <set>
#include <stack>
using namespace std;
string input;
int matching[221], brkNum = 0; 
bool erasing[221]; 
set<string> retSet;
string ret;

void eraseBrackets(int cur){
    //기저사례 : 문자열을 완성
    if(cur == input.length()){
        retSet.insert(ret);
        return;
    } 
    if(input[cur] == '('){  
        //괄호를 지우는 경우
        erasing[matching[cur]] = true;
        eraseBrackets(cur+1);   
        erasing[matching[cur]] = false;
    }
    if(input[cur] ==')'&&erasing[cur]){
        //짝괄호를 지운 경우 
        eraseBrackets(cur+1);
    }
    //괄호,짝괄호를 안지우거나 일반 문자열일 경우. 
    else{
        ret+=input[cur];
        eraseBrackets(cur+1);
        ret.resize(ret.size()-1);
    }
}

//괄호 매칭 설정 
void matchBrackets(string& input){
    stack<int> st;
    for(int i = 0; i<input.length();i++){
        if(input[i] == '(') st.push(i);
        else if(input[i] == ')'){
            //매칭이 되는 괄호를 저장한다. 
            matching[i] = st.top();
            matching[st.top()] = i;     
            st.pop();
            brkNum++;
        }
    }
}
int main(){
    cin>>input;
    matchBrackets(input);
    eraseBrackets(0);
    retSet.erase(input);
    set<string>::iterator it;
    for(it = retSet.begin(); it!=retSet.end(); it++)
        cout<<(*it)<<endl;
}