문제

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

풀이

예외적인 테스트 케이스를 생각하지 못해서 계속 "틀렸습니다"를 받았던 문제다.

이 블로그를 읽고나서, 괄호가 제거된 문자열들은 vector가 아니라 set에 저장해야 한다는 걸 알 수 있었다.

위의 예시처럼 서로 다른 괄호를 제거했는데 동일한 문자열이 나오는 경우가 있기 때문에, 결과 값을 set에 저장해서 중복을 제거해야 한다. 그리고 set은 내부적으로 균형 이진트리로 구현되어 있어서 원소들이 자동 정렬된다.

예외적인 테스트 케이스까지 잘 고려해서 문제를 풀어야 한다는 걸 배웠다. 그리고 set 자료구조의 특징에 대해서도 알 수 있었다.

prev_permutation

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

vector<pair<int, int>> paren; 
set<string> result; 

void saveParenthesesPosition(string input) {
	stack<pair<char, int>> st;
	
	for(int i = 0; i < input.size(); i++){
		char ch = input[i];

		if(ch == '('){
			int openIdx = i; 
			st.push({ch, openIdx});
		}

		if(ch == ')'){
			int openIdx = st.top().second; 
			int closeIdx = i; 

			// 괄호 쌍의 인덱스를 저장한다. 
			paren.push_back({openIdx, closeIdx});

			// 스택의 top에 있는 여는 괄호를 꺼낸다. 
			st.pop(); 
		}
	}
}

string removeParentheses(string str, int idx){
	int left = paren[idx].first; 
	int right = paren[idx].second; 

	str.replace(left, 1, " ");
	str.replace(right, 1, " ");

	return str;
}

void solution(int n, string input){
	for(int r = 1; r <= n; r++){
		vector<int> arr(n);
		for(int i = 0; i < n; i++){
			arr[i] = i; 
		}
		
		vector<bool> selected(n, false);
		for(int i = 0; i < r; i++){
			selected[i] = true; 
		}

		do{
			string str = input;
			for(int i = 0; i < n; i++){
				if(selected[i]){ // 1~r개 선택 
					str = removeParentheses(str, arr[i]);
				}
			}

			// 공백 제거 후 set에 저장하기 (중복되는 문자열 없도록)
			str.erase(remove(str.begin(), str.end(), ' '), str.end());
			result.insert(str);
		}while(prev_permutation(selected.begin(), selected.end()));  
	}
}

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

	string input; 
	cin >> input; 

	saveParenthesesPosition(input);
	solution(paren.size(), input);

	for(auto e: result){
		cout << e << "\n"; 
	}
	
	return 0; 
}

백트래킹

내 풀이

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

const int MAX = 10; 
vector<bool> selected(MAX, false); 
vector<int> arr(MAX, 0); 

vector<pair<int, int>> paren; 
set<string> result; 
int n = 0, r = 0; 
string input; 

string removeParentheses(string str, int idx){
	int left = paren[idx].first; 
	int right = paren[idx].second; 

	str.replace(left, 1, " ");
	str.replace(right, 1, " ");

	return str; 
}

void dfs(int idx, int cnt){ // 숫자 번호, 뽑은 개수 
	if(cnt == r){
		// 문자열에서 괄호 쌍 r개를 제거한다. 
		string str = input;
		for(int i = 0; i < r; i++){
			str = removeParentheses(str, arr[i]);
		}
		str.erase(remove(str.begin(), str.end(), ' '), str.end());
		result.insert(str);
		return; 
	}

	for(int i = idx; i < n; i++){ // idx부터 시작 
		if(!selected[i]){
			selected[i] = true; 
			
			arr[cnt] = i; // 선택된 값을 저장한다. 
			dfs(i, cnt + 1); 
			
			selected[i] = false; 
		}
	}
}

void saveParenthesesPosition() {
	stack<pair<char, int>> st;
	
	for(int i = 0; i < input.size(); i++){
		char ch = input[i];

		if(ch == '('){
			int openIdx = i; 
			st.push({ch, openIdx});
		}

		if(ch == ')'){
			int openIdx = st.top().second; 
			int closeIdx = i; 

			// 괄호 쌍의 인덱스를 저장한다.
			paren.push_back({openIdx, closeIdx});

			// 스택의 top에 있는 여는 괄호를 꺼낸다. 
			st.pop(); 
		}
	}

	n = paren.size();
}

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

	cin >> input; 
	
	saveParenthesesPosition();
	
	for(r = 1; r <= n; r++){
		dfs(0, 0);

		fill_n(selected.begin(), n, false); 
		fill_n(arr.begin(), n, 0); 
	}
	
	for(auto e: result){
		cout << e << "\n"; 
	}
	
	return 0; 
}

다른 풀이

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

const int MAX = 201; 
bool removed[MAX]; // 괄호 쌍의 삭제 여부  
vector<pair<int, int>> paren; // 괄호 쌍의 인덱스 
stack<int> st; 
set<string> answer; // 중복 제거 & 오름차순 정렬 
string input; 

// 입력 문자열에서 괄호 쌍의 인덱스를 벡터에 저장한다.
void saveParenthesesIndex() {
	for(int i = 0; i < input.size(); i++){
		if(input[i] == '(') {
			st.push(i);
			continue; 
		}
	
		if(input[i] == ')') {
			paren.push_back({st.top(), i});
			st.pop();
		}
	}
}

void dfs(int idx, int removedCount) {
    // 1개 이상의 괄호 쌍을 삭제한 문자열 저장 
	if(removedCount >= 1) {
		string temp = "";
		for(int i = 0; i < input.size(); i++){ 
			if(!removed[i]) temp += input[i]; 
		}

        // 중복 제거 & 오름차순 정렬 
		answer.insert(temp); 
	}

	for(int i = idx; i < paren.size(); i++) { // idx부터 시작 
        // 상태 변화 
		removed[paren[i].first] = true; 
		removed[paren[i].second] = true; 
		
        // 재귀 호출 
		dfs(i + 1, removedCount + 1);
		
        // 상태 복구 
		removed[paren[i].first] = false; 
		removed[paren[i].second] = false; 
	}
}

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

	cin >> input; 

	saveParenthesesIndex();

	dfs(0, 0);

	for(auto str: answer){
		cout << str << "\n"; 
	}
	
	return 0;
}