[백준,c++] 2800번 - 괄호 제거

문제

2800번: 괄호 제거

 

코드

#include <iostream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

bool except[201];
vector<pair<int,int>>close;
stack<int> open;
set<string> ans;
string s;

void dfs(int index, int delete_cnt){
    
    if(delete_cnt >= 1){
        string temp = "";
        for(int i=0; i<s.length(); i++){
            if(!except[i]) temp+=s[i];
        }
        ans.insert(temp);
    }
    
    for(int i=index; i<close.size(); i++){
        except[close[i].first] = 1;
        except[close[i].second] = 1;
        dfs(i+1, delete_cnt+1);
        except[close[i].first] = 0;
        except[close[i].second] = 0;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    
    cin>>s;
    for(int i=0; i<s.length(); i++){
        if(s[i]=='(') open.push(i);
        else if(s[i]==')'){
            close.push_back({open.top(), i});
            open.pop();
        }
    }
    dfs(0,0);
    
    for(auto it=ans.begin(); it!=ans.end(); it++){
        cout<<*it<<'\n';
    }
}

 

풀이

백트랙킹의 비중이 높았던 문제였습니다.

문제 풀이의 핵심 아이디어는 다음과 같습니다.

1. 열린 괄호일때는 stack에 인덱스 번호를 넣는다.
2. 닫힐 괄호일때는 vector에 pair형태로 괄호의 쌍을 저장한다.

예를 들어 "(0/(0))"를 입력이라고 가정하면 vector<pair<int,int>> v = { {3, 5}, {0, 6} } 이 될 것입니다.

그 후 이제 백트랙킹을 이용하여 조합을 구하면 됩니다. 제거한 쌍들은 except라는 방문 배열을 통해 기록하였으며, 하나 이상의 쌍을 제거했을 때 수식을 찾도록 지정했습니다.

  다만 "( ( ( 0 ) ) ) ( 1 )" 의 입력이 주어질 때  괄호 중에서는 중복된 형태가 존재할 수 있습니다.

• 가장 바깥쪽부터 1, 2, 3번으로 순서대로 번호를 붙여봤을 때,
• 1번 괄호만 제거하고 출력한 결과 = ( ( 0 ) ) ( 1 )
• 2번 괄호만 제거하고 출력한 결과 = ( ( 0 ) ) ( 1 )
• 3번 괄호만 제거하고 출력한 결과 = ( ( 0 ) ) ( 1 )
• 출처: https://yabmoons.tistory.com/352 

따라서 set을 이용하여 중복을 제거해 주었고, 마찬가지로 문제에서 "서로 다른 식을 사전 순으로 출력한다." 조건 또한 set을 이용하면 오름차순으로 자동으로 정렬이 되기에 간편하게 해결할 수 있습니다.