어흥
[백준 2800] 괄호 제거 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/2800
1. 주의할 점
- 출력 결과로 서로 다른 문자열을 사전순으로 출력해야 한다
2. 구현
- Stack을 통해 개구간과 폐구간을 계산하여 쌍을 이룰 경우 각각 Open, Close 벡터에 인덱스 번호를 추가한다
- DFS() 함수를 통해 최대 2^10-1의 경우를 계산하며, 일부 괄호를 제거한 문자열의 경우 Set에 추가하여 중복을 제거한다
- C++에서 Set은 사전정렬이므로 Set의 begin부터 end까지 순서대로 출력한다
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
using namespace std;
vector<int> open, close;
set<string> s;
string str;
bool avail[200];
void dfs(int idx, int cnt) {
if (idx == open.size()) {
if (cnt > 0) {
string temp = "";
for (int i = 0; i < str.size(); i++)
if (avail[i])
temp += str[i];
s.insert(temp);
}
return;
}
//삭제X
dfs(idx + 1, cnt);
//삭제
avail[open[idx]] = false;
avail[close[idx]] = false;
dfs(idx + 1, cnt + 1);
avail[open[idx]] = true;
avail[close[idx]] = true;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> str;
stack<int> st;
for (int i = 0; i < str.size(); i++) {
//초기화
avail[i] = true;
char c = str[i];
if (c == '(') st.push(i);
else if (c == ')') {
int oidx = st.top();
st.pop();
open.push_back(oidx);
close.push_back(i);
}
}
dfs(0,0);
for (auto it = s.begin(); it != s.end();it++) {
cout << *it << '\n';
}
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 11003] 최솟값 찾기 (C++) (0) | 2021.08.20 |
---|---|
[백준 10986] 나머지 합 (C++) (3) | 2021.08.18 |
[백준 12904] A와 B (C++) (0) | 2021.08.07 |
[백준 17265] 나의 인생에는 수학과 함께 (Java) (6) | 2021.07.27 |
[백준 22116] 창영이와 퇴근 (Java) (0) | 2021.07.27 |
Comments