[BOJ] 백준 2800. 괄호 제거 (Gold V)

5월에 카카오 월간 코드 챌린지를 치고 나서, 

내 약점 중 하나인 스택을 보완해야겠다고 느끼고 풀어본 문제이다.

 

문제는 아래와 같다.

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

2800번: 괄호 제거

---

의식의 흐름 및 해설

우선 올바른 괄호쌍끼리만 제거할 수 있다는 점을 파악한다.

따라서 "문자열 폭발" 과 비슷한 원리를 이용할 수 있으며, 이 괄호쌍들을 넣을지 안넣을지 고려하는 알고리즘을 짜봐야 하는데, 괄호쌍은 적어도 1, 많아도 10 이하이기 때문에 백트래킹 알고리즘을 이용해도 O(2^10)이므로 시간초과가 나지 않는다. 괄호쌍을 넣을지 안넣을지 여부는 괄호쌍끼리의 index를 따로 저장해 bool visit[201] 배열을 만들어 이를 이용해 백트래킹을 하였다.

 

또한, 사전순으로 정렬해야 하기 때문에, 정답에 해당하는 문자열을 vector에 집어넣고 사전 순 정렬 후 중복을 제거해주는 코드인 v.erase(unique(v.begin(), v.end()), v.end()); 를 이용해준다.

 

참고로 stack과 vector는 같은 원리이므로 나는 stack 대신 vector를 이용했으며,

vector<pair<char, int>> st 와 같이 char형만 들어가 있는 것이 아니므로, string(st.begin(), st.end())와 같이 이용하는 것은 불가능했다. 다만, 괄호쌍은 두 글자밖에 안되기 때문에 단순히 스택의 top()과 그 다음 top()이 서로 ()를 이루는지만 확인해주면 됐다.

---

시행착오

처음에 백트래킹할 때 코드를 아래와 같이 짰다.

	for (int i = 0; i < ans.size(); i++) {
		visit[ans[i].first] = true;
		visit[ans[i].second] = true;
		solve(cur + 1);
		visit[ans[i].first] = false;
		visit[ans[i].second] = false;
	}

ans는 괄호 순서쌍의 인덱스가 저장돼있는 벡터이다.

당연히 현재 ans[i]보다 이전 인덱스의 순서쌍 인덱스는 이미 확인한 상태이므로, 따로 확인할 필요가 없는데 내가 백트래킹에서 주로 하는 실수인 for(int i=cur이 아닌 0 (cur로 해야 함);i<ans.size();i++) 으로 작성하였다.

따라서 아래 코드로 수정하였다.

	for (int i = cur; i < ans.size(); i++) {
		solve(cur + 1);
		visit[ans[i].first] = true;
		visit[ans[i].second] = true;
		solve(cur + 1);
		visit[ans[i].first] = false;
		visit[ans[i].second] = false;
	}

그런데, 이렇게 수정해도 메모리초과가 난다.

애초에 for문을 따로 돌 필요가 없다. 

이미 dfs 재귀적으로 도는데 뭐하러 for문을 이용해 시간복잡도를 O(2^(N*N))으로 만든단 말인가.

따라서 아래와 같이 수정해주었다.

	solve(cur + 1);
	visit[ans[cur].first] = true;
	visit[ans[cur].second] = true;
	solve(cur + 1);
	visit[ans[cur].first] = false;
	visit[ans[cur].second] = false;

그 외 스택을 이용하여 괄호순서쌍을 구해주는 부분은

카카오 월간 코드 챌린지에서 이미 한번 당했고, 최근에 4949번 문제, 9935번 문제를 풀면서 익혔기 때문에 크게 어렵지 않았다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int MAX = 201;
vector<pair<int, int>> ans;
vector<string> res;
string s;
bool visit[MAX];
void solve(int cur) {
	if (cur == ans.size()) {
		string str;
		for (int j = 0; j < s.length(); j++) {
			if (visit[j])
				continue;
			str += s[j];
		}
		if (str != s)
			res.push_back(str);
		return;
	}
	solve(cur + 1);
	visit[ans[cur].first] = true;
	visit[ans[cur].second] = true;
	solve(cur + 1);
	visit[ans[cur].first] = false;
	visit[ans[cur].second] = false;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> s;
	vector<pair<char, int>> st;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '(' || s[i] == ')') {
			st.push_back({ s[i], i });
		}
		if (st.size() >= 2 && st[st.size()-2].first=='(' 
			&& st[st.size()-1].first==')') {
			ans.push_back({ st[st.size() - 2].second, st[st.size() - 1].second });
			st.pop_back();
			st.pop_back();
		}
	}
	solve(0);
	sort(res.begin(), res.end());
	res.erase(unique(res.begin(), res.end()), res.end());
	for (auto i : res) {
		cout << i << "\n";
	}
}

---

스택이랑 벡터가 유사하다는 점을 최근에 다시 상기하게 됐다.

내가 벡터를 하도 자주 쓰다보니 의도치 않게 스택문제인데 인지하지 못하고 잘 해결해버린 케이스가 많았는데, 이게 나에게 큰 독이 된 듯하다. 카카오 월간 코드 챌린지 3번 문제들은 매번 나한테 자극이 되주는 듯하다.

 

월간코드챌린지 너무 재밌는데 시즌3도 열렸음 좋겠다.

그땐 3번 해결할 수 있도록 해보자.