백준 2800 괄호 제거 c++

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

2800번: 괄호 제거

 

문제 접근은 간단했다.

괄호쌍을 인덱스 기준 pair로 묶어줘서 1~ 괄호쌍의 개수만큼 백트래킹 하면된다.

 

 

** 서로 다른 식 ** 을 제대로 읽지 않아서 20분 넘게 왜 틀렸는지만 보고있었다.

첫 코드때는 백트래킹할때 서로 다른 식 고려를 안한탓에 map 컨테이너에 넣지않고 dfs_combination 함수에서 바로 출력을 했다.

 

서로 다른식을 고려하려면 map컨테이너를 이용해 중복을 제거해준 뒤 dfs_combination이 끝나고 출력해주면 된다.

 

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <map>
using namespace std;

bool check[201];
bool c[11];
string str;
map<string,int> ma;
vector<pair<int,int> > rem_index;	// 첫번째 여는괄호 두번째 닫는괄호 
									// 인덱스정보 저장
									
void dfs_combination(int x,int cnt,int y)
{
	if(cnt == y) {
		string tmp;
		bool last_c[201] = {false, };
		for(int i=0; i<rem_index.size(); i++) {	
			if(c[i]) {
				last_c[rem_index[i].first] = true;
				last_c[rem_index[i].second] = true;
			}
		}
		for(int i=0; i<str.length(); i++) {
			if(!last_c[i]) {
				tmp = tmp + str[i];
			}
		}
		ma[tmp]++;
	}
	
	for(int i=x; i<rem_index.size(); i++) {
		if(c[i])	continue;
		c[i] = true;
		dfs_combination(i,cnt+1,y);
		c[i] = false;
	}
	
}

int main(void)
{
	// **pair로 괄호쌍 구분**
	// dfs_combination 이용해서 괄호 제거 식 출력 
	cin >> str;	
	stack<int> stk;				
	
	for(int i=0; i<str.length(); i++) {
		if(str[i] == '(') {
			stk.push(i);
		}
		else if(str[i] == ')') {
			rem_index.push_back({stk.top(),i});
			stk.pop();
		}
	}
	
	
	for(int i=1; i<=rem_index.size(); i++) {
		dfs_combination(0,0,i);
	}
	
	for(auto const &pair : ma) {
		cout << pair.first << endl;
	}
	
	return 0;
}