[ 백준 ] 2800번 - 괄호 제거(C++)

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

2800번: 괄호 제거

 

 

[ 문제풀이 ]

 

1. 수식을 입력받아 각 괄호에 번호를 붙입니다.

 

2. 조합을 이용하여 각 괄호들을 제거해주고, set 자료구조에 저장하여 중복을 제거해줍니다.

 

3. 저장된 답을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<string>
#include<stack>
#include<set>
 
using namespace std;
 
string str;
int arr[200];
set<string> ans;
int visited[11];
int cnt;
 
void dfs(int limit, int level, int num)
{
    if (level == limit) {
        string temp = "";
        for (int i = 0; i < str.size(); i++) {
            if (visited[arr[i]] != 1) {
                temp += str[i];
            }
        }
 
        ans.insert(temp);
        return;
    }
 
    for (int i = num; i <= cnt; i++) {
        visited[i] = 1;
        dfs(limit, level + 1, i + 1);
        visited[i] = 0;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> str;
    stack<int> s;
 
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            cnt++;
            arr[i] = cnt;
            s.push(cnt);
        }
        else if (str[i] == ')') {
            arr[i] = s.top();
            s.pop();
        }
    }
 
    for (int i = 1; i <= cnt; i++) {
        dfs(i, 0, 1);
    }
 
    for (auto& next : ans) {
        cout << next << '\n';
    }
}