백준 2800 괄호 제거

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 괄호쌍이 위치해 있는 인덱스를 저장 한 후 함수의 재귀 호출로 해결을 하여야 합니다. 

 

'('을 만났을 경우 그 짝인 괄호를 지우는 경우와 지우지 않는 경우로 나누어서 진행 하면 해당 하는 모든 경우를 구할 수가 있습니다.

 

즉 입력받은 문자열을 비어있는 문자열에 처음부터 더해가며 '('가 나왔을 경우 이 괄호를 제거하고 가는 경우, 그렇지 않은 경우를 재귀적 호출로 모두 구해낼수가 있습니다.

 

계속 시간 초과가 나서 다른분들 풀이를 참고하여 풀었는데 재귀 함수는 역시 어려운것 같습니다..

 

#include <iostream>
#include <stack>
#include <string>
#include <set>


using namespace std;

set<string> se; //가능한 경우를 저장할 set 
stack<char> s;
int index[200]; //괄호 쌍의 인덱스를 저장 
string ret;
bool erase[200]; // 괄호를 지울지 말지를 결정 

void deletefunc(int cur, int len, string str) {
	
	if(cur == len) {
		se.insert(ret);
		return;
	}
	
	if(str[cur] == '(') {
		erase[index[cur]] = true; //괄호를 지우는 경우 
		deletefunc(cur+1, len, str);
		erase[index[cur]] = false; //괄호를 지우지 않는 경우 
	}
	
	if(str[cur] == ')' && erase[cur]) {
		deletefunc(cur+1, len, str);
	} 
	
	else {
		ret += str[cur];
		deletefunc(cur+1, len, str);
		ret.resize(ret.size()-1); // 더해준 만큼 감소시킴 
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	string str;
	cin >> str;
	int len = str.length();

	for(int i = 0; i < len; i++) { //스택에 '('가 나올시 인덱스를 저장 
		if(str[i] == '(') {
			s.push(i);
		}

		else if(str[i] == ')') { //')'가 나올경우  index[i]에 '('가 있는 인덱스를 저장 
			index[i] = s.top();
			index[s.top()] = i; //괄호 쌍을 서로 매칭 시켜줌  ex) 1,3번째에 '(' ')' 가 있다면 index[1] = 3, index[3] = 1 과 같은식 
			s.pop();
		}
	}

	deletefunc(0, len, str);

	se.erase(str);
	
	for(auto n: se)
		cout<<n<<'\n';

	return 0;
}