[G4] 백준 2800번 괄호 제거 C++ 스택, set, 백트래킹

리뷰

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

그냥 되는데로 막 풀었는데 이게 왜 맞지? 싶었던 문제

수식의 길이가 짧고, 괄호 쌍이 많아야 10개라 시간 초과는 나지 않은 것 같다.

 

 

전역 변수

• n : 주어지는 수식의 길이를 저장할 변수
• cnt : 괄호 쌍의 개수를 저장할 변수
• si : 열린 괄호의 인덱스를 저장할 정수형 벡터
• ei : 닫힌 괄호의 인덱스를 저장할 정수형 벡터
• ans : 괄호를 제거한 문자열을 저장하기 위한 문자열 형식의 set
• s : 주어지는 수식을 입력 받을 문자열 변수

 

함수

1. bt

void bt(int level, string str)

 

괄호를 제거한 모든 수식을 탐색하기 위한 백트래킹 함수

1. 매개 변수로 재귀 레벨 level과 현재 문자열 str을 입력 받는다.
2. 만약 재귀가 한번이라도 진행된 상태라면 문자열을 set에 추가하는 작업을 진행한다.
3. 빈 문자열 temp를 초기화 하고, str를 탐색하며 공백(' ')이 아닌 문자라면 temp에 더해준다.
4. 위 조건을 만족하여 만들어진 문자열 temp를 ans에 insert해준다.
5. level이 cnt에 도달하였다면 기저조건에 해당하므로 return을 해준다.
6. 기저조건에 해당하지 않는다면 재귀 단계를 올려 bt를 실행해 준다. (문자열이 변경되지 않은 상태)
7. 그 다음엔 level을 index로 사용해 si[level], ei[level]에 해당하는 인덱스를 문자열 str에서 공백으로 변경해준다.
8. 한번 더 재귀 단계를 올려 bt를 실행해 준다. (문자열이 변경된 상태)

 

문제풀이

1. 수식을 문자열 s에 입력 받아주고, n을 s의 크기로 저장해 준다.
2. 괄호 정보를 저장하기 위한 정수형 벡터 stack을 초기화 해준다.
3. n번의 반복문을 실행하고 문자열에서 '('를 만난 경우 스택에 인덱스를 추가해 준다.
4. 만약 ')'를 만난 경우 si에 stack의 맨 뒤에 저장된 인덱스를 저장하고, ei에 현재 인덱스를 저장한다.
5. 이후 스택의 맨 뒤 요소를 빼주고 cnt를 증가시켜 준다.
6. bt 함수에 재귀 단계 0과 초기 문자열 s를 인자로 전달하여 백트래킹을 시작한다.
7. 탐색을 마친 뒤 ans에 초기 문자열 s가 포함되어 있다면 제거해 준다.
8. ans에 저장된 문자열을 줄 바꿈을 구분하여 출력해 준다.

 

참고 사항

오름 차순과 중복 제거를 사용하기 위해 set를 사용해 주었다.

다 풀고 나서 생각해 보니 백트래킹에서 level이 존재할 때만 ans에 추가해줄 필요는 없을 것 같다.(어차피 들어감)

따라서 백트래킹 후 초기 문자열은 꼭 ans에서 제거해 주어야 한다.

 

 

정답 코드

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

int n, cnt;
vector<int> si;
vector<int> ei;
set<string> ans;
string s;

void bt(int level, string str) {
	if (level) {
		string temp = "";
		for (const char& ch : str) if (ch != ' ') temp += ch;
		ans.insert(temp);
	}
	if (level == cnt) return;
	
	bt(level + 1, str);
	str[si[level]] = ' ';
	str[ei[level]] = ' ';
	bt(level + 1, str);
}

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

	cin >> s;
	n = s.size();
	vector<int> stack;
	for (int i = 0; i < n; ++i) {
		if (s[i] == '(') stack.push_back(i);
		else if (s[i] == ')') {
			si.push_back(stack.back());
			ei.push_back(i);
			stack.pop_back();
			cnt++;
		}
	}
	bt(0, s);
	ans.erase(s);
	for (const string r : ans) cout << r << "\n";
}