[C/C++] 백준 - 2800번 : 괄호 제거

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

2800번: 괄호 제거

괄호 관련 문제는 대부분 스택을 이용한다. 

이 문제 또한 스택을 이용해야 하는데 스택 뿐만 아니라 재귀함수로 각 문자열을 만들어주어야한다.

스택을 이용하는 부분은 괄호의 쌍을 묶어주는 부분이다.

 

여는 괄호는 스택에 넣어주고 닫는 괄호가 나오면 스택의 top부분이 닫는 괄호와 쌍이 된다는 걸 알 수 있다.

이걸 이용하여 괄호의 쌍을 pair형태로 저장 할 수가 있다. 그럼 총 n쌍의 괄호쌍을 저장할 수 있고,

재귀함수를 통해 1부터 n쌍을 제거할 수 있다.

 

pair형태로 괄호 index가 저장되어있기 때문에 괄호 index를 제외한 나머지 부분 문자열을 저장해주는 것이다.

주의할 점이 중복제거를 해주어야한다. 나도 중복제거를 하지않아 처음에 틀렸다고 떴다.

 

정렬을 하게되면 중복되는 문자열들은 연속적으로 저장되어있기 때문에 전 문자열을 저장해주는 형태로 중복출력을 

피할 수 있다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <map> 
#include <algorithm>
#include <cmath>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define INF 987654321
#define Mod 10007
#define endl '\n'
#define pil pair<int,int>

using namespace std;

string s; 
bool visited[12];
bool chk[203];
vector<string> answer;
vector<pair<int, int>> v;

void func(int N, int depth, int start) {
	if (depth == N) {
		memset(chk, false, sizeof(chk));
		for (int i = 0; i < 11; i++) {
			if (visited[i]) {
				int fst = v[i].first;
				int scd = v[i].second;

				chk[fst] = true;
				chk[scd] = true;
			}
		}
		string Temp;
		for (int i = 0; i < s.size(); i++) {
			if (chk[i]) continue;
			Temp += s[i];
		}
		answer.push_back(Temp);
		Temp.clear();
		return;
	}

	for (int i = start; i < v.size(); i++) {
		if (!visited[i]) {
			visited[i] = true;

			func(N, depth + 1, i + 1);

			visited[i] = false;
		}
	}
}

int main() {
	CUNLINK;
	cin >> s;
	stack<int> stk;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '(') {
			stk.push(i);
		}
		else if (s[i] == ')') {
			v.push_back({ stk.top(), i });
			stk.pop();
		}
	}
	sort(v.begin(), v.end());
	for (int i = 1; i <= v.size(); i++) {
		func(i, 0, 0);
	}
	sort(answer.begin(), answer.end());
	cout << answer[0] << endl;
	string prev = answer[0];
	for (int i = 1; i < answer.size();i++) {
		if (prev == answer[i]) continue;
		cout << answer[i] << endl;
		prev = answer[i];
	}
	
	return 0;
}