BOJ - 2800번 괄호 제거(C++)

문제 출처: https://www.acmicpc.net/problem/2800

문제 난이도

Gold 5

문제 접근법

DFS를 이용해서 하나둘씩 문자열을 찾으면 된다.
주의할 점은 괄호 하나씩을 체크하는게 아니라 괄호 쌍으로 체크해야한다.

통과 코드

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

using namespace std;

bool visited[201];
bool ch[201];
set<string> ans;
string str;
vector<pair<int, int>> p;

void dfs(int cnt, int idx) {
	if (cnt >= 1) {
		string s = "";
		for (int i = 0; i < str.size(); i++) {
			if (ch[i]) continue;
			s += str[i];
		}
		ans.insert(s);
	}
	for (int i = idx; i < p.size(); i++) {
		if (visited[i]) continue;
		visited[i] = true;
		ch[p[i].first] = true;
		ch[p[i].second] = true;
		dfs(cnt + 1, idx + 1);
		visited[i] = false;
		ch[p[i].first] = false;
		ch[p[i].second] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> str;
	stack<int> s;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {
			s.push(i);
		}
		else if (str[i] == ')') {
			p.push_back({ s.top(), i });
			s.pop();
		}
	}
	dfs(0, 0);
	for (auto x : ans) {
		cout << x << "\n";
	}
	return 0;
}

피드백

처음에 그냥 괄호 따로씩 하다가 틀렸다. 예제만 나와서 괜찮을 줄 알았는데 질문 검색란에 있는 반례를 돌리니깐 완전 아닌 걸 알았다. 괄호 쌍으로 해야하는 걸 파악을 못해서 결국 다른 코드를 참고하게 됐는데 이런 센스 좀 길러야겠다!