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

문제 링크: https://www.acmicpc.net/problem/2800

2800번: 괄호 제거

1. 주의할 점

- 출력 결과로 서로 다른 문자열을 사전순으로 출력해야 한다

 

2. 구현

- Stack을 통해 개구간과 폐구간을 계산하여 쌍을 이룰 경우 각각 Open, Close 벡터에 인덱스 번호를 추가한다

- DFS() 함수를 통해 최대 2^10-1의 경우를 계산하며, 일부 괄호를 제거한 문자열의 경우 Set에 추가하여 중복을 제거한다

- C++에서 Set은 사전정렬이므로 Set의 begin부터 end까지 순서대로 출력한다

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
using namespace std;
vector<int> open, close;
set<string> s;
string str;
bool avail[200];

void dfs(int idx, int cnt) {
	if (idx == open.size()) {
		if (cnt > 0) {
			string temp = "";
			for (int i = 0; i < str.size(); i++)
				if (avail[i])
					temp += str[i];
			s.insert(temp);
		}
		return;
	}
	//삭제X
	dfs(idx + 1, cnt);
	//삭제
	avail[open[idx]] = false;
	avail[close[idx]] = false;
	dfs(idx + 1, cnt + 1);
	avail[open[idx]] = true;
	avail[close[idx]] = true;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> str;
	stack<int> st;

	for (int i = 0; i < str.size(); i++) {
		//초기화
		avail[i] = true;

		char c = str[i];
		if (c == '(') st.push(i);
		else if (c == ')') {
			int oidx = st.top();
			st.pop();
			open.push_back(oidx);
			close.push_back(i);
		}
	}
	dfs(0,0);
	for (auto it = s.begin(); it != s.end();it++) {
		cout << *it << '\n';
	}
	return 0;
}