(BOJ) 2800 괄호 제거

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

문제 풀이:

<main>

- 스택을 이용해서 괄호 위치 쌍으로 저장

  1. 입력받은 문자열을 처음부터 보면서 '('이 나오면 stack에 그 위치 push

  2. ')'이 나오면 stack.top()과 현재 위치를 (pos)벡터에 따로 저장하고 stack.pop()

<function>

- 재귀함수 이용해서 어떤 괄호를 지울지 지정 

  1. 비트 마스크로 지울 괄호 번호 표시 (괄호 번호=위의 2번에서 벡터 번호)

  2. 어떤 괄호를 지울지 다 정했으면 그 괄호들의 위치를 priority_queue에 넣는다 

  3. 입력받은 문자열을 임시 변수에 옮기면서 priority_queue.top() (지울 괄호 중 가장 먼저 나오는 것)은 패스하고 저장

  4. 옮겨진 임시 변수 값을 res라는 벡터에 저장

<main>

- res 벡터 sort

- 순서대로 출력하되 중복되는 문자열이 존재할 수 있으므로 전에 출력한 문자열과 같으면 출력하지 않고 패스

* 중복되는 문자열이 존재하는 이유

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

즉, ((0)) 꼴도 가능하다.

위 같은 경우 괄호의 위치를 저장 할 때 (0,4)와 (1,3)이 저장된다.

(0,4)만 지우는 경우와 (1,3)만 지우는 경우의 결과가 동일하다.

 

-> 이거 안 읽어서 틀림..... 문제를 잘 읽도록 하자!

소스코드:

#include <iostream> #include <queue> #include <vector> #include <string> #include <string.h> #include <stack> #include <algorithm> #define inf 987654321 using namespace std; string s; vector<string> res; vector<pair<int, int>> pos; void func(int cur, int state) { if (cur == pos.size()) { if (pos.size() != 0 && state == 0) return; priority_queue<int> pq; for (int i = 0; i < pos.size(); i++) { if (state&(1 << i)) { pq.push(-pos[i].first); pq.push(-pos[i].second); } } string t = ""; for (int i = 0; i < s.size(); i++) { if (!pq.empty()&&-pq.top() == i) pq.pop(); else t += s[i]; } res.push_back(t); return; } func(cur + 1, state); func(cur + 1, state | (1 << cur)); } int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> s; stack<int> st; for (int i = 0; i < s.size(); i++) { if (s[i] == '(') { st.push(i); } else if (s[i] == ')') { pos.push_back({ st.top(),i }); st.pop(); } } func(0, 0); sort(res.begin(), res.end()); cout << res[0] << '\n'; for (int i = 1; i < res.size(); i++) { if ( res[i] == res[i - 1]) continue; cout << res[i] << '\n'; } return 0; }