[백준 C++ 2800][G5] 괄호 제거

⭐️ 난이도

 

Gold 5

---

⭐️ 문제

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

2800번: 괄호 제거

 

 

---

⭐️ Idea flow

 

올바른 괄호 쌍을 지워야 한다는 부분에서 이전에 스택을 이용해서 풀었던 문제가 생각났다.

하지만 괄호의 제거함으로써 얻을 수 있는 모든 수식을 얻어야 하고, 이는 괄호 쌍의 모든 조합을 찾아야 한다는 뜻이다.

 

모든 조합을 찾기 위해서는 백트래킹(DFS)가 적절하기 때문에 이를 활용하기 위해서는 괄호쌍에 대한 정보를 가공해야 할 필요가 있었다.

 

먼저 수식을 받고, 수식을 반복문으로 한 글자씩 확인하면서 

1) ( : 열린 괄호 일 때에는 stack에 해당 인덱스를 저장

2) ) : 닫힌 괄호 일 때에는 stack.top(열린 괄호의 인덱스)와 현재 인덱스(닫힌 괄호의 인덱스)를 pair 객체로 묶어 vector에 저장한다.

 

이후에는 백트래킹을 실행하는데 괄호 쌍의 인덱스(정보)를 vector에 저장했기 때문에 vector에서 괄호 쌍을 최소 1개부터 최대 괄호 쌍의 개수(vector의 size)개를 선택(제거)하면 된다.

 

백트래킹의 과정은 다음과 같다.

1) vector에 저장되어 있는 괄호 쌍을 반복문을 통해 index 0부터 vector의 size까지 선택해야 한다.

   이 때, 현재 선택한 괄호 쌍의 다음 인덱스를 DFS의 매개변수로 전달한다.

2) 만일 선택된 괄호 쌍의 갯수가 1개 이상이라면 선택된 괄호 쌍을 제외한 수식을 생성한다.

   그리고 set에 저장한다. (set에 저장하는 이유 : 중복을 막기 위해서)

3) DFS가 모두 호출되어 DFS 다음 코드가 작동될 때 선택된 괄호 쌍을 선택 취소하여 다양한 조합을 만든다.

 

재귀를 통한 백트래킹이 완료되었다면 가능한 수식 조합이 set에 저장되어 있을 것이다.

이 때, set은 자동으로 정렬을 해주기 때문에 set의 begin 부터 end 까지 차례대로 출력을 하면 된다.

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>

using namespace std;

// 2800 - 괄호 제거
string str;
vector<int> isSelected, isVisited(10, false); // 전체 문자열에서 쓰인 인덱스, info에서 쓰인 인덱스
vector<pair<int, int>> info; // 열린 괄호, 닫힌 괄호 쌍의 인덱스 저장
set<string> result;

void input(){
    cin >> str;
    isSelected.assign(str.length(), false);

    stack<int> stk;
    for(int i = 0; i < str.length(); i++){
        if(str[i] == '('){
            stk.push(i);
        }
        else if(str[i] == ')'){
            int idx = stk.top();
            stk.pop();
            info.emplace_back(make_pair(idx, i));
        }
    }
}

void DFS(int idx, int cnt){
    if(cnt >= 1){ // 선택(제거)된 괄호의 쌍이 1개 이상이라면
        string s = "";
        for(int i = 0; i < str.length(); i++){
            if(isSelected[i])   continue;
            s += str[i];
        }
        if(!result.count(s)){
            result.insert(s);
        }
    }

    for(int i = idx; i < info.size(); i++){
        if(isVisited[i])    continue;
        isVisited[i] = true;
        isSelected[info[i].first] = true;
        isSelected[info[i].second] = true;

        DFS(i + 1, cnt + 1);

        isVisited[i] = false;
        isSelected[info[i].first] = false;
        isSelected[info[i].second] = false;
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    DFS(0, 0);

    for(auto iter = result.begin(); iter != result.end(); iter++){
        cout << *iter << '\n';
    }
    
    return 0;
}