baekjoon 2800:괄호 제거

baekjoon 2800 괄호 제거

2800번 괄호 제거

접근

괄호를 제거할 때 여는 괄호와 닫는 괄호 쌍을 맞추는게 중요한데 이 작업은 stack을 이용해서 했다.
그리고 이진수를 이용해서 어느 괄호를 지울지 경우의 수 생성을 했고 지울 괄호는 N으로 표시했다가 마지막에
N이면 무시하게 해서 괄호를 지웠다. 이번에도 map에 넣어서 자동 정렬시켰다.

코드

//2800
#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  string s;
  cin >> s;
  vector<char> v;
  map<string, int> ans;
  int count = 0;
  vector<pair<int, int>> brace;
  stack<int> st;
  for(int i = 0; i < s.size(); i++){
    v.push_back(s[i]);
    if(s[i] == '('){
      count++;
      st.push(i);
    }
    else if(s[i] == ')'){
      brace.push_back({st.top(), i});
      st.pop();
    }
  }
  int ansCount = (1 << count) - 2;
  for(int i = 0; i <= ansCount; i++){
    vector<char> temp;
    temp = v;
    for(int j = 0; j < count; j++){
      if(!(i & (1 << j))){
        temp[brace[j].first] = 'N';
        temp[brace[j].second] = 'N';
      }
    }
    string tempStr = "";
    for(auto i : temp){
      if(i != 'N'){
        tempStr += i;
      }
    }
    ans[tempStr] = 0;
  }
  for(auto i : ans){
    cout << i.first << "\n";
  }
  //2*10-2 11111 11111 no
  //1022 ~ 0 1023

  return 0;
}

배운 점

괄호나오면 stack 자주 쓴다. (저번에 후위표기식postfix 할 때도 그랬다.)