[BOJ/백준][Gold5] 2800 : 괄호 제거 (C++)

https://www.acmicpc.net/problem/2800

2800번: 괄호 제거

 

 

[난이도] Gold5
[유형] 스택

[풀이]
stack을 이용해 모든 괄호쌍의 위치를 저장한 뒤,
괄호쌍을 고르는 모든 경우의 수를 브루트포스를 이용해 구해준 뒤,
선택된 괄호쌍의 괄호들을 제거한 string을 set에 저장한 뒤 순회하며 출력해주면 됩니다.
괄호쌍의 최대 개수가 10개로 제한되어 있으므로 브루트포스를 이용할 수 있습니다.

 

#include <iostream>
#include <string>
#include <stack>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
string s;
vector<pair<int,int>> v;
int main(){
    cin >> s;
    stack<int> st;
    for(int i=0;i<s.size();i++){
        char c = s[i];
        if(c=='(') st.push(i);
        else if(c==')'){
            v.push_back({st.top(),i});
            st.pop();
        }
    }
    set<string> ans;
    int n = v.size();
    for(int i=1;i<(1<<n);i++){
        vector<bool> erased(s.size());
        for(int j=0;j<n;j++){
            if(((1<<j)&i)>0) erased[v[j].first]=erased[v[j].second]=1;
        }
        string tmp;
        for(int j=0;j<s.size();j++){
            if(!erased[j]) tmp+=s[j];
        }
        ans.insert(tmp);
    }
    for(auto a : ans) cout << a << '\n';
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2800.cpp