백준, BOJ, 1741번, 괄호제거 C++ [CPP] ★★★★

실수하기 쉬운 문제고

나도 실수했다.

그리고 처음부터 생각하기는 쉽지 않다.

비트마스킹으로 풀만한 문제였다.

2^10 = 1024

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

2800번: 괄호 제거

 

 

 

 

 

---

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;


//괄호를 "한 쌍"씩 뺀 경우, 집어넣은 경우 => 모든 경우해야할듯
int maxNum = 0;

stack<int> pos;
vector<pair<int,int>> pairPos;
set<string> answer; //괄호를 제거한 후의 식 모음

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

    //괄호는 쌍을 이룸
    int index = 0;
    for(char c : s){
        if(c == '('){
            pos.push(index); //열린 괄호의 위치
        }else if(c == ')'){
            //올바른 괄호만 주어지므로 stack에 맨 위에있는 괄호에 대해서 닫힌 괄호이다.
            int openIdx = pos.top();
            int closeIdx = index;
            pairPos.push_back({openIdx, closeIdx});
            pos.pop();
        }
        index++;
    }
    
    //모든 괄호의 위치를 알게 되었으니 브루트포스로 모든 괄호를 조사한다.
    //괄호 쌍의 수
    maxNum = pairPos.size();
    
    //최대 괄호가 10개이기 때문에 10개 비트마스킹으로 가능 2^10 = 1024
    for(int i = 1; i<(1<<maxNum); i++){
        vector<bool> checked(s.size());
        //범위 0~9 (10가지 경우 대해 AND 연산)
        //=> 현재  비트 상태가 j 원소를 넣을 것인지 말것인지 조사
        for(int j = 0; j<maxNum; j++){
            if(((1<<j)&i)>0) checked[pairPos[j].first] = checked[pairPos[j].second] = 1;
        }
        string now;
        for(int j=0; j<(int)s.size(); j++){
            if(!checked[j]) now +=s[j];
        }
        //괄호를 빼도 같은 식이면 세지 않음
        answer.insert(now);
    }
    for(auto ans : answer){
        cout << ans << '\n';
    }
    return 0;
}