백준 4817 괄호 (C++)

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

4817번: 괄호

재귀함수나 스택을 사용하는 문제였습니다. 저같은 경우 스택을 잘 못써서 재귀를 사용해 풀었습니다.

 

손으로 예제를 들어서 풀어보시면 괄호를 못없애는 경우는 괄호 안에 덧셈이 들어가있으며 

괄호 앞 뒤로 곱하기가 들어가있는경우 뿐인걸 아실 수 있습니다. 

 

따라서 재귀적으로 가장 바깥에 있는 괄호부터 풀어가시면서  그 괄호안에 덧셈이 들어가있는 경우만 체크해서 앞뒤로 곱하기가 있는지만 확인하고 괄호를 없애면 됩니다.

 

또한 유의해야되는 경우는 가장 바깥에 있는 괄호를 벗기는 작업인데 가장 처음 발견한 괄호의 크기가 현재 탐색중인 범위와 같으면 가장 바깥에 있는 괄호이므로 벗기면됩니다.

 

저같은 경우 코드가 좀 난잡한데 더 깔끔하게 푸실 수 있을것같습니다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
vector<int> vec;
bool chk[2001];
string input;
int t;
int recur(int l, int r){
    if(l>=r) return -1;
    int temp=0;
    int templ=-1;
    int ret=2;
    for(int x=l;x<=r;x++){
        if(input[x]=='(') {
            temp++;
            if(temp==1) templ=x;
        }
        if(input[x]==')'){
            temp--;
            if(temp==0){
                int k=recur(templ+1,x-1);
                if(templ==l && x==r){
                    chk[templ]=true;
                    chk[x]=true;
                    return k;
                }
                if(k==1){
                    if(templ-1>=0){
                        if(input[templ-1]>='a' && input[templ-1]<='z') continue;
                        if(input[templ-1]==')') continue;
                    }
                    if(x+1<t){
                        if(input[x+1]>='a' && input[x+1]<='z') continue;
                        if(input[x+1]=='(') continue;
                    }
                }
                chk[templ]=true;
                chk[x]=true;
            }
        }
        if(temp==0 && input[x]=='+') ret=1;
    }
    return ret;
    
}
int main(){
    while(cin>>input){
        for(int x=0;x<input.size();x++) chk[x]=false;
        t=(int)input.size();
        recur(0,t-1);
        for(int x=0;x<t;x++){
            if(!chk[x]){
                cout<<input[x];
            }
        }
        cout<<'\n';
    }
}