BOJ 2800 괄호제거

• 문제 해석

문제를 읽었을 때, 가장 집중했던 부분은 괄호에 대한 부분이었다. 
일반적으로 괄호에 대해 언급이 이뤄지면 이는 스택을 활용할 가능성이 높기 때문이다.
다만, 기존의 스택의 활용 문제와는 달리 이번 문제는 스택의 활용법이 달랐다.
기존 문제의 경우에는 "(" 를 입력 받았을 때, push하고 ")"를 입력받았을 때, pop을
하면 풀리는 문제였지만 이번 문제의 경우에는 여러 개의 괄호쌍이 제거되어 만들어지는 
모든 경우의 식을 찾아야 하기 때문이다. 따라서 ")" 를 입력받았을 때, pop을 하는 것이 
아니라 괄호쌍에 대한 index를 pair로 기록을 하고 이를 활용한 백트래킹 기법으로
모든 경우의 수를 찾고자 했다.

• 구현

#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<set>
using namespace std;

string str;
stack<int> s; // 괄호쌍 찾기
int cnt = 0; // 괄호의 갯수
pair<int, int> T[12]; // 괄호쌍 idx 표시
bool check[201];
set<string> ans;


void dfs(int size, int cur) {
	if (size == 0) {
		string st = "";
		for (int i = 0; i < str.size(); i++) {
			if (!check[i]) {
				st += str[i];
			}
		}
		ans.insert(st);
		return;
	}

	for (int i = cur; i < cnt; i++) {
		if (!check[T[i].first]) {
			check[T[i].first] = true;
			check[T[i].second] = true;
			dfs(size - 1, i + 1);
			check[T[i].first] = false;
			check[T[i].second] = false;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> str;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {
			s.push(i);
		}
		else if (str[i] == ')') {
			T[cnt] = { s.top(), i };
			s.pop();
			cnt++;
		}
	}

	for (int i = 1; i <= cnt; i++) {
		dfs(i, 0);
	}

	for (auto a : ans)
		cout << a << "\n";
}

• 피드백

코드를 제출하는 과정에서 오류가 발생했었는데 그것은 출력값의 중복을 체크해주지 
못한 부분이었다. 만약 ((((((1)))))) 과 같은 입력을 받았을 때, 나의 코드로는
중복된 값을 배출하게 된다. 따라서 중복을 막을 수 있는 간편한 자료구조인 "set"을 
이용했고 set의 기본 정렬값이 사전식 정렬이었기에 완벽한 선택이었다. 
이 외에도 코드를 여러 개 제출하며 흥미로운 것도 발견했는데, 이는 cnt 변수의 유무였다.
혹시 몰라서 탐색 수를 최소화하기 위한 장치로 심어두었는데 cnt 변수 없이 구현을 했을 땐,
시간 초과가 나고 cnt 변수를 활용하게 되면 정답이 되곤 했다.