[baekjoon 2800] 괄호 제거 (스택, 구현, 재귀) (C++)

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

2800번: 괄호 제거

주어진 문자열에서 괄호 쌍을 제거해서 만들 수 있는 문자열을 모두 출력하는 문제이다.

 

괄호가 3쌍이 있다면, 0 1 2 01 02 12 012를 지울 수 있다.

그래서 조합을 통해 숫자들을 만들고, 저 번호에 해당하는 괄호의 쌍을 지우면 되겠다고 생각을 했다.

 

처음에 아무 생각 없이 (1+(2*(3+4))) 이런 경우만 생각해서 그때마다 괄호의 개수를 세서 괄호를 지워줬는데, (1)*(2)*(3)의 경우도 있었다. 

따라서, 처음에 괄호의 쌍에 대한 정보를 저장해주고 시작해야 한다. pair로 괄호에 대한 인덱스 정보로 묶어주었다.

 

그리고 (((1)))(2)의 경우, 괄호가 총 4개가 있고 저 조합을 통해 지워준다면

1번 2번 3번 괄호를 지울 때 똑같은 문자열이 나온다. (((1)))은 어떤 괄호를 지워도 같은 경우가 있다.

그래서 중복제거도 해줘야 하는 문제이다.

 

나는 그래서 set을 이용해서 중복제거, 사전 순 정렬까지 한꺼번에 해결했다.

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

using namespace std;

stack<int> pairStack;
vector<pair<int, int>> pairVector;
int check[11], stringCheck[201];
string s;
set<string> answer;

void combination(string s, int depth, int next, int to) {
	if (depth == to+1)
		return;
	if (depth > 0) {
		string temp = "";
		for (int i = 0; i < s.size(); i++) {
			if (!stringCheck[i])
				temp += s[i];
		}
	
		answer.insert(temp);
	}
	for (int i = next; i < to; i++) {
		if (!check[i]) {
			check[i] = true;
			stringCheck[pairVector[i].first] = true;
			stringCheck[pairVector[i].second] = true;
			combination(s, depth + 1, i + 1, to);
			stringCheck[pairVector[i].first] = false;
			stringCheck[pairVector[i].second] = false;
			check[i] = false;
		}
	}
}

int main() {
	ios::sync_with_stdio(false); 	cin.tie(0);
	cin >> s;
	string temp = "";
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '(') {
			pairStack.push(i);
		}
		else if (s[i] == ')') {
			pairVector.push_back({ pairStack.top(), i });
			pairStack.pop();
		}
	}

	combination(s, 0, 0, pairVector.size());

	for (auto k : answer)
		cout << k << "\n";
}