[백준 2800번] 괄호 제거

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

괄호 제거 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	510	137	110	29.178%

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

예제 입력 1 

(0/(0))

예제 출력 1 

(0/0)
0/(0)
0/0

#include <iostream>
#include <stack>
#include <string>
#include <set>
using namespace std;
 
int cnt;           //괄호 개수
int match[201];    //괄호 짝 맞추기 괄호가 있는 자리를 저장
stack <int> mat;   //괄호 짝 맞추기 위해서 일시적으로 사용하는 스택
char cop[201];     //수식 char 형태로 저장
string input;      //수식 초기 input
set <string> ret;  //사전순으로 정렬하고 중복을 삭제하기 위해 set사용
 
void comb(int *set, int set_size, int m, int n, int index);
void setmat();
void sort(int *set, int set_size);
 
int main() {
 
    int i = 0;
    int *set;   //조합 경우의 수를 담을 포인터
 
    cin >> input;
 
    //괄호 개수 세기
    for (i = 0; i < input.length(); i++) {
        if (input.at(i) == '(') cnt++;
    }
 
    set = new int[cnt];   //괄호 개수만큼 동적할당
    setmat();
 
    //경우의 수 만큼 시도
    for (i = 1; i <= cnt; i++)   comb(set, 0, cnt, i, 0);
 
    //ret 모두 출력
    while (!ret.empty()) {
        cout << *ret.begin() << endl;
        ret.erase(ret.begin());
    }
 
    delete set;
 
    return 0;
}
 
void comb(int *set, int set_size, int m, int n, int index) {
 
    // 종료
    if (set_size == n) {
        //식을 함수에서 사용하기 편하게 char 형식으로 정렬
        for (int i = 0; i < input.length(); i++) {
            cop[i] = input.at(i);
        }
 
        sort(set, set_size);
        return;
    }
 
    if (m == index) return;
 
    // 분기
    set[set_size] = index;
    comb(set, set_size + 1, m, n, index + 1);
 
    comb(set, set_size, m, n, index + 1);
 
}
 
void setmat() {
 
    for (int i = 0; i < input.length(); i++) {
 
        //'('의 자리 위치를 mat에 넣음
        if (input.at(i) == '(') {
            mat.push(i);
        }
            //')'가 나오면 match에 짝을 맞추어서 자리를 서로 바꾸어 넣음 ex) match[1] = 3 -> match[3] = 1
        else if (input.at(i) == ')') {
            match[i] = mat.top();
            match[mat.top()] = i;
            mat.pop();
        }
    }
 
}
 
void sort(int *set, int set_size) {
 
    int i, j;
    int count = 0;  //괄호가 들어올 때 count
    string temp;    //set에 넣기 전에 임시 저장
 
    for (i = 0; i < input.length(); i++) {
 
        if (cop[i] == '(') {
 
            for (j = 0; j < set_size; j++) {
                //'('를 삭제해야 할 때 그에 맞는 짝 ')'도 함께 '#'로 변경
                if (count == set[j]) {
                    cop[match[i]] = '#';
                    cop[i] = '#';
                }
            }
 
            count++;
        }
    }
 
    for (i = 0; i < input.length(); i++) {
        //미리 변경해둔 '#'를 제외하고 삽입
        if (cop[i] != '#') temp.push_back(cop[i]);
    }
 
    ret.insert(temp);
 
}