[백준 2800] 괄호제거(C++)

📕문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를 들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

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

---

📕입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

---

📕출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

---

📕문제해석

괄호의 대응되는 방식을 알아야 함.

• 괄호의 종류는 왼쪽 괄호, 오른쪽 괄호가 있다.--> ( , )
• 대응되는 순서는 가장 나중에 등장한 왼쪽 괄호와 가장 먼저 등장한 오른쪽 괄호가 대응된다.
• 이때의 index를 pair를 사용해서 넣어준다.

• 여기서 pop_back()을 해주는 이유는 왼쪽 괄호와 오른쪽 괄호가 서로 짝을 찾았기 때문에 다음 왼쪽 괄호에 대응되는 오른쪽 괄호를 찾아주기 위해서 빼준다.

visit 배열은 str배열과 동일시되는데 해당 index에 str을 넣어줄지 말지를 결정하는 배열임.

 

재귀를 통해서 모든 조합을 탐색해줌.

• pair의 first는 왼쪽 괄호의 index, second는 오른쪽 괄호의 index이다.
• 해당 괄호를 포함시키고 싶지 않을 때 true로 초기화하고 재귀 함수를 호출해서 문자열에 넣어준다.

문자열 생성

• visit [j]가 true인 부분은 포함하지 않게 문자열을 생성해주고 괄호를 제거했는데, 만약 문자열이 같은 경우가 있을 수 있기 때문에 map의 개념을 사용해서 중복되지 않고, 자동으로 오름차순 정렬되게 넣어준다.

---

💡코드

/* 2800 괄호 제거
괄호를 제거해서 만들수  있는 수식을 모두 만들기
stack에 넣기
만들수 있는  경우의 수는 2^(괄호의수)-1이다.
왼쪽에서 가장 뒤에 있는 괄호와 오른쪽에서 앞에 있는 괄호룰 지워준다.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
string str;
vector<int> symbol;
vector<pair<int, int>> p;
vector<int> visit;
void check(int i, int Count);
map<string,int>m;
int main()
{
    cin >> str;
    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] == '(')
        {
            symbol.push_back(i); //왼쪽 괄호의 index를 넣음.
        }
        else if (str[i] == ')')
        {
            //가장 최근에 symbol에 넣어준 왼쪽 괄호의 index값과 가장 먼저 등장한 오른쪽 괄호가 서로 대응되기 때문에 
            //그때의 index를 pair에 넣어줌.
            int num = symbol[symbol.size() - 1]; 
            symbol.pop_back();      
            p.push_back(make_pair(num, i));      
        }
    }
    visit.resize(str.length(), 0); //visit의 size를 str과 동일하게 초기화해줌.
    check(0, 0);
    for(auto iter=m.begin();iter!=m.end();iter++) //map에는 자동으로 오름차순 정렬되고, first를 전부 출력함.
    {
        cout<<iter->first<<endl;
    }
}
void check(int i, int Count)
{
    if (Count > 0)
    {
        string s = "";
        for (int j = 0; j < visit.size(); j++)
        {
            if (visit[j] == true)
                continue; // true라면 문자열에 포함x
            else
            {
                s += str[j]; //내가 포함하고싶지 않은 문자열을 뺴고 넣어줌.
            }
        }
        m.insert(make_pair(s,1)); //괄호를 제거하더라도 중복된 문자열이 있을수 있으므로, map을 사용함.
    }
    for (int k = i; k < p.size(); k++)
    {
        if (visit[p[k].first] == true && visit[p[k].second] == true) //만약 이미 했던 경우의 수라면 넘어감.
        { //이미 사용한 괄호라면
            continue;
        }
        //괄호를 저장하지 못하게 초기화
        visit[p[k].first] = true;     
        visit[p[k].second] = true;    
        check(k, Count + 1); 
        //괄호를 다시 포함하게 초기화
        visit[p[k].first] = false;
        visit[p[k].second] = false;
    }
}

---

✔느낀 점

• 처음에 괄호의 위치를 저장했지만, pair의 개념을 사용하지 않고 각각의 vector를 만들어서 따로 저장했다.
• 괄호의 위치를 저장하는 것은 어렵지 않았지만, 경우의 수를 찾는 것이 어렵지 않았다.
  • 처음에는 순열의 조합 개념을 사용해서 풀려고 했지만, 구현하기가 어려웠다.
  • 그래서 모든 경우의 수를 탐색할 수 있는 dfs를 통해서 구현했다.
• 처음에 중복된 문자열이 있다는 것을 생각 못했는데 (((1)))은 어떤 괄호를 처음에 제거하더라도 ((1))이 되기 때문에 중복이 발생한다는 것을 깨닫고 map을 사용했다.
• dfs는 자주 쓰이니까 계속 훈련하는 것이 좋겠다.