[백준] 괄호제거_2800_C++

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

2800번: 괄호 제거

 

풀이

괄호를 보자마자 스택을 먼저 떠올렷습니다.

괄호의 개수가 최대 10개이므로 조합으로 풀 수 있다고 생각하여 재귀를 이용한 조합을 사용하였습니다.

재귀를 실행하기전에 괄호의 위치를 미리 저장해줬습니다.(여는거,닫는거 세트로)

C++의 set은 저장하면 사전순으로 자동 정렬되는 성질을 이용하여 set에 저장하였습니다.

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

using namespace std;

string str;
vector<string> ans;
set<string> s;
bool visit[200];

vector<int> open, close;

// idx : 몇번째 괄호를 제거할지
// cnt : 몇개의 괄호를 제거한 재귀인지
void go(int idx, int cnt) {
	if (idx == open.size()) {
		if (cnt > 0) {
			string result = "";
			for (int i = 0; i < str.size(); i++) {
				if (visit[i])
					result += str[i];
			}
			//cout << result << endl;
			s.insert(result);
		}
		return;
	}

	// 괄호 그대로
	go(idx + 1, cnt);
	// 괄호 삭제
	visit[open[idx]] = false;
	visit[close[idx]] = false;
	go(idx + 1, cnt + 1);
	visit[open[idx]] = true;
	visit[close[idx]] = true;
}

int main() {
	// c++ 입출력 빠르게 해주는 코드
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> str;
	stack<int> st;

	for (int i = 0; i < str.length(); i++) {
		visit[i] = true;

		// 여는괄호의 인덱스를 스택에 저장(닫는괄호와 페어를 이루기위해서)
		if (str[i] == '(')
			st.push(i);
		else if (str[i] == ')') {
			int idx = st.top();
			st.pop();
			// 닫는괄호가 나왓다면 닫는괄호와 여는괄호의 인덱스를
			// 세트로 저장해준다.
			open.push_back(idx);
			close.push_back(i);
		}
	}

	go(0, 0);
	// set은 알아서 사전순으로 정렬됨
	for (auto& i : s) {
		cout << i << endl;
	}
}