취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2800번 문제인 괄호 제거이다.
문제는 아래 링크를 확인하자.

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

이 문제는 주어진 수식 문자열에서 짝이 맞는 괄호들을 일부 제거한 문자열들을 사전순으로 출력하는 문제이다.

문자열을 둘러보며 짝이 맞는 괄호쌍의 위치를 스택을 이용하여 구해주고, 이 쌍들을 각각 포함하는 경우와 포함하지 않는 경우를 전부 탐색하여 한 벡터에 담은 뒤 정렬하는 것으로 문제를 해결할 수 있다.

식 하나를 여러 쌍의 괄호가 감쌀 경우 위와 같이 처리한 경우 중복되는 수식이 나온다는 점을 유의하여 구현하자. 예를 들면 ((((1+2))))와 같은 수식의 처리에 유의하자.

아래는 제출한 소스코드이다.

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

int arr[201];
int P, slen;
vector<pair<int, int>> p_pair;
string s;
vector<string> ans;

void func(int N) {
	if (N == P) {
		string ret = "";
		for (int i = 0; i < slen; i++) {
			if (arr[i]) continue;
			ret += s[i];
		}
		ans.emplace_back(ret);
	}
	else {
		int x = p_pair[N].first, y = p_pair[N].second;
		arr[x] = arr[y] = 1;
		func(N + 1);
		arr[x] = arr[y] = 0;
		func(N + 1);
	}
}

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

	stack<int> stk;
	cin >> s;
	slen = s.length();
	for (int i = 0; i < slen; i++) {
		if (s[i] == '(') stk.push(i);
		else if (s[i] == ')') {
			p_pair.push_back({ stk.top(),i });
			stk.pop();
		}
	}

	P = p_pair.size();
	
	func(0);

	sort(ans.begin(), ans.end());
	
	int len = ans.size();
	for (int i = 1; i < len; i++) {
		if (ans[i] == ans[i - 1]) continue;
		cout << ans[i] << '\n';
	}
}