[BOJ - 2800] 괄호 제거

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

 

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

 

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

 

풀이

첫 코드는 pair, stack, set을 사용해서 풀었다.

처음에 문자열을 입력 받은 후에 ( 가 있는 index와 쌍을 이루는 ) 가 있는 index를 묶어서 vector에 push_back하였다.

그 이후에는 dfs를 통해서 해당 문자를 추가할지 뺄지 결정하는데 만약 visited[idx]가 1이라면 ) 라는 의미이고 이미 쌍을 이루는 ( 가 삭제되었다과 판단하여 string에 추가하지 않는다.

만약 str[idx]가 (라면 v[idx]가 empty인지 확인해주고(=예제에서 잘못된 문자열이 주어질 경우 대비) visited[v[idx][0]] 을 1로 설정한다.

또한 )가 아니라면 해당 값을 넣은 경우도 else에서 진행한다.

 

코드

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

stack<pair<char, int>>stk;
vector<int>v[202];
string str;
set<string>str_set;

int isValid(string s) {
	stack<char> clause;
	for (char c : s) {
		if (c == '(') {
			clause.push(c);
		}
		else if (c == ')') {
			if (clause.empty() || clause.top() != '(') {
				return 0;
			}
			clause.pop();
		}
	}
	return clause.empty() ? 1 : 0;
}

void dfs(string s, int visited[202], int idx) {
	if (idx == str.length()) {
		if (isValid(s) && s != str) {
			str_set.insert(s);
		}
		return;
	}
	else {
		// '('거나 대칭 ')'인 경우 skip
		if (str[idx] == '(' && !v[idx].empty()) {
			visited[v[idx][0]] = 1;
			dfs(s, visited, idx + 1);
			visited[v[idx][0]] = 0;
		}
		if (visited[idx]) {
			dfs(s, visited, idx + 1);
		}
		else {
			dfs(s + str[idx], visited, idx + 1);
		}
	}
}

int main() {
	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') {
			stk.push({ str[i], i });
		}
		else if (str[i] == ')') {
			if (!stk.empty() && stk.top().first == '(') {
				v[stk.top().second].push_back(i);
				stk.pop();
			}
		}
	}
	int visited[202] = {};
	dfs("", visited, 0);
	for (string item : str_set) {
		cout << item << "\n";
	}
	return 0;
}