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

백준의 괄호제거(2800) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 괄호를 제거해서 나올 수 있는 모든 식을 출력해야 하는 문제이다.

   본인은 가장 먼저 "부분집합"을 구현하였다.

   예제입력1을 한번 봐보자. 식이 ( 0 / ( 0 ) ) 으로 주어졌다. 이 때 괄호는 총 2쌍이 있고 괄호를 제거해서 나올 수 있는

   결과는 예제출력과 같이 3개가 존재한다.

   괄호를 1개 지웠을 때 식이 2개가 나오고, 2개 모두 지웠을 때 또 다른 식이 1개가 나오게 된다.

   즉, 1개 지웠을 때 발생할 수 있는 모든 경우 체크, 2개 지웠을 때 발생할 수 있는 모든 경우를 체크해주면 된다.

   부분집합을 구현하는 것은 조합에서 종료조건문만 달리 설정해 주면 된다.

   조합을 아직 구현하는 법을 모른다면 아래의 글을 읽고 오도록 하자.

   [ 조합 구현하는 법(Click) ]

 

2) 부분집합을 구현함으로써 발생할 수 있는 괄호 중에서는 중복된 형태가 존재할 수 있다.

   예를 들어서 다음과 같은 경우이다.

   ( ( ( 0 ) ) ) ( 1 ) 같은 형태를 봐보자.

   0 을 둘러싼 괄호가 총 3쌍이 있다. 가장 바깥쪽부터 1, 2, 3번으로 순서대로 번호를 붙여봤을 때,

   1번 괄호만 제거하고 출력한 결과 = ( ( 0 ) ) ( 1 )

   2번 괄호만 제거하고 출력한 결과 = ( ( 0 ) ) ( 1 )

   3번 괄호만 제거하고 출력한 결과 = ( ( 0 ) ) ( 1 )

   과 같이 분명 다른 괄호를 제거했음에도 결과가 똑같은 경우가 있다.

   따라서, 중복된 결과를 제거하기 위해서 set을 사용해서 문자열의 중복을 처리해 주었다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
 
#define endl "\n"
#define MAX 210
using namespace std;
 
string MAP;
vector<string> Answer;
vector<pair<int, int>> GwalHo;
set<string> Visit;
bool Select[10];
bool Express_MAP[MAX];
 
void Input()
{
    cin >> MAP;
    deque<int> Q;
    for (int i = 0; i < MAP.length(); i++)
    {
        if (MAP[i] == '(') Q.push_back(i);
        else if (MAP[i] == ')')
        {
            int P = Q.back();
            Q.pop_back();
            GwalHo.push_back(make_pair(P, i));
        }
    }
}
 
void DFS(int Idx, int Cnt)
{
    if (Cnt >= 1)
    {
        string S = "";
        for (int i = 0; i < MAP.length(); i++)
        {
            if (Express_MAP[i] == true) continue;
            S = S + MAP[i];
        }
        
        if (Visit.find(S) == Visit.end())
        {
            Visit.insert(S);
            Answer.push_back(S);
        }
    }
 
    for (int i = Idx; i < GwalHo.size(); i++)
    {
        if (Select[i] == true) continue;
 
        Select[i] = true;
        Express_MAP[GwalHo[i].first] = true;
        Express_MAP[GwalHo[i].second] = true;
        DFS(i, Cnt + 1);
        Select[i] = false;
        Express_MAP[GwalHo[i].first] = false;
        Express_MAP[GwalHo[i].second] = false;
    }
}
 
void Solution()
{
    DFS(0, 0);
    sort(Answer.begin(), Answer.end());
    for (int i = 0; i < Answer.size(); i++)
    {
        cout << Answer[i] << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}