[백준 2800번 C/C++] 괄호 제거

 

[백준 2800번 C/C++] 괄호 제거

 

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

---

 

 

해결전략

 

문자열

재귀

비트마스킹 Bitmasking

 

---

 

 

정답코드 1 - 비트마스킹 사용

 

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

string input; // 문제에서 주어진 문자열
int n;
vector<pair<int, int>> brackets; // 괄호 한 쌍의 위치를 저장
set<string> results; 			 // 만들 수 있는 문자열을 기록

// 괄호 쌍의 위치를 찾는 함수
void FindBrackets()
{
	stack<int> bracketLocation;

	// 문자열을 순회하며 괄호 쌍을 찾음
	for (int i = 0; i < input.size(); i++)
	{
		if (input[i] == '('){
			bracketLocation.push(i); // '(' 위치를 스택에 저장
		}
		else if (input[i] == ')'){
			int openBracketLocation = bracketLocation.top(); // 마지막으로 열린 괄호 위치를 가져옴
			bracketLocation.pop(); // 스택에서 '(' 제거

			brackets.push_back({ openBracketLocation, i }); // 괄호 쌍의 위치를 벡터에 저장
		}
	}
}

// 재귀적으로 문자열을 생성하는 함수
void Generate(int idx, string str, const vector<int> ch)
{
	if (idx == n){
		results.insert(str);
		return;
	}

	if (ch[idx] == 1) // idx 위치의 문자 생략
	{
		Generate(idx + 1, str, ch);
	}
	else // idx 위치의 문자 추가
	{
		Generate(idx + 1, str + input[idx], ch);
	}
}

// 가능한 모든 괄호 조합을 생성하는 함수
void Cal()
{
	for (int bitmask = 1; bitmask < (1 << brackets.size()); bitmask++)
	{
		vector<int> ch(n, 0); // 문자를 제거할지 여부를 표시하는 벡터 (0: 유지, 1: 제거)

		// bitmask의 각 비트를 확인하여 괄호 쌍을 제거할지 결정
		for (int i = 0; i < brackets.size(); i++)
		{
			if (bitmask & (1 << i)) {		// 비트마스크의 i번째 비트가 설정되어 있으면
				ch[brackets[i].first] = 1;	// 여는 괄호 위치를 제거로 표시
				ch[brackets[i].second] = 1;	// 닫는 괄호 위치를 제거로 표시
			}
		}

		Generate(0, "", ch); // 현재 제거 설정에 따라 문자열을 생성
	}
}

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

	cin >> input;
	n = input.size();

	FindBrackets(); // 괄호 쌍의 위치를 찾음
	Cal(); // 괄호 조합을 이용하여 문자열을 생성

	for (const auto& iter : results)
	{
		cout << iter << "\n";
	}

	return 0;
}

 

 

---

 

정답코드 2

 

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

string input; // 문제에서 주어진 문자열
int n;
vector<pair<int, int>> brackets; // 괄호 한 쌍의 위치를 저장
set<string> results; // 만들 수 있는 문자열을 기록

void FindBrackets()
{
	stack<int> bracketLocation;

	for (int i = 0; i < input.size(); i++)
	{
		if (input[i] == '('){
			bracketLocation.push(i);
		}
		else if (input[i] == ')'){
			int openBracketLocation = bracketLocation.top();
			bracketLocation.pop();

			brackets.push_back({ openBracketLocation, i });
		}
	}
}

void Generate(int idx, string str, const vector<int> ch)
{
	if (idx == input.size()){
		results.insert(str);
		return;
	}

	if (ch[idx] == 1) // idx 위치의 문자 생략
	{
		Generate(idx + 1, str, ch);
	}
	else // 문자 생략X
	{
		Generate(idx + 1, str + input[idx], ch);
	}
}

void CalHelper(int cnt, vector<int>& ch)
{
	if (cnt == brackets.size()) {
		Generate(0, "", ch);
		return;
	}

	// 현재 괄호 쌍을 제거하지 않는 경우
	CalHelper(cnt + 1, ch);

	// 현재 괄호 쌍을 제거하는 경우
	ch[brackets[cnt].first] = 1;
	ch[brackets[cnt].second] = 1;
	CalHelper(cnt + 1, ch);
	ch[brackets[cnt].first] = 0;
	ch[brackets[cnt].second] = 0;
}

void Cal()
{
	vector<int> ch(n, 0);

	CalHelper(0, ch);
}

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

	cin >> input;
	n = input.size();

	FindBrackets();
	Cal();

	int i = 0;
	for (const auto& iter : results)
	{
		i++;
		if (i == 1) continue;
		cout << iter << "\n";
	}

	return 0;
}

 

---

 

 

 

정답코드 3

 

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

string input;
set<string> results;
vector<pair<int, int>> brackets;

void Generate(int idx, string str, vector<int>& ch)
{
	if (idx == input.size()){
		results.insert(str);
		return;
	}

	if (ch[idx] == 1){
		Generate(idx + 1, str, ch);
	}
	else if (ch[idx] == 0){
		Generate(idx + 1, str + input[idx], ch);
	}
}

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

	cin >> input;

	// 괄호 위치 구하기
	stack<int> bracketLoc;
	for (int i = 0; i < input.size(); i++)
	{
		if (input[i] == '('){
			bracketLoc.push(i);
		}
		else if (input[i] == ')'){
			int openLoc = bracketLoc.top();
			bracketLoc.pop();
			brackets.push_back({ openLoc, i });
		}
	}

	// 전체 경우의 수 1 << brackets.size() - 1 
	for (int bitmask = 1; bitmask < (1 << brackets.size()); bitmask++)
	{
		vector<int> ch(input.size(), 0);

		for (int i = 0; i < brackets.size(); i++)
		{
			if (bitmask & (1 << i)){
				ch[brackets[i].first] = 1;
				ch[brackets[i].second] = 1;
			}
		}

		Generate(0, "", ch);
	}

	// 결과 출력
	for (const auto& iter : results){
		cout << iter << "\n";
	}

	return 0;
}

 

 

---