백준[2800] 괄호 제거

문제 설명

문제 링크

http://icpc.me/2800

2800번: 괄호 제거

풀이

백트래킹과 스택을 이용하여 풀 수 있다.

우선 여는 괄호와 닫는 괄호의 짝을 찾아 이것을 인덱스로 가지고 있어야 한다.

이 짝을 찾기 위해서 스택을 이용한다. )를 만날 때 까지 스택에 모두 push하다가 ) 를 만날때 ( 를 만날 때까지 pop을 하고 처음 만난 (가 )의 짝이다.

위에 구해둔 괄호 쌍을 이용하여 백트래킹을 한다. 백트래킹을 해도 괄호가 최대 10개이기 때문에 O(2^10)이다.

백트래킹은 괄호를 쓸 때와 쓰지 않을 때로 나누어 진행한다.

이때 중복되는 문자열이 생길 수 있는데 이것은 erase와 unique함수를 이용하여 처리한다.

코드

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

using namespace std;

vector<pair<int, int>> idxSet;
stack<pair<char, int>> st;
vector<string> ans;
bool check[202];
string s;

void solve(int cur) {
    if (cur == idxSet.size()) {
        string tmp;
        for (int i = 0; i < s.size(); i++) {
            if (!check[i]) tmp.push_back(s[i]);
        }
        if (tmp != s) ans.push_back(tmp);
        return;
    }
    auto &[s, e] = idxSet[cur];
    solve(cur + 1);
    check[s] = check[e] = true;    
    solve(cur + 1);
    check[s] = check[e] = false;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ')') {
            string tmp;
            while (st.top().first != '(') {
                tmp.push_back(st.top().first);
                st.pop();
            }
            idxSet.push_back({st.top().second, i});
            st.pop();
        } else {
            st.push({s[i], i});
        }
    }
    solve(0);
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    for (auto &c : ans) {
        cout << c << "\n";
    }
}