백준 문제 24552번 올바른 괄호 문제풀이 c++

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

24552번: 올바른 괄호

 

문제해석

 

답이되는 경우가 항상 1이상이므로 ( 와 )의 갯수차이는 항상 1이다.

 

(의 개수가 )보다 1많은 경우를 살펴보자

()(() 같은경우 2번째 닫는 괄호까지는 올바른 괄호문자열이되고 3번째부터 올바르지 않은 문자열이 된다.

3번째 문자열부터 존재하는 (를 아무거나 하나 지워버리면 올바른 문자열이된다.

 

)의 개수가 (보다 1많은 경우 역시 비슷하게 마찬가지이다.

뒤에서 부터 올바르지 않은 괄호열이 되는 시작점을 찾은후에 거기서부터 처음까지 )의 개수를 세주면된다.

()(())) 같은경우 처음부터 올바르지 않으므로 끝부터 처음까지의 )의 개수 4가 정답이된다.

 

근데 나는 귀찮아서 )개수가 (보다 1많은경우 괄호열을 180도 뒤집어 버린후 (가 )보다 1많은 경우로 생각해서 풀었다.

 

 

코드

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int a[100001];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    string s;
    cin>>s;
    int open=0;
    int close=0;
    for(int i=0; i<s.size(); i++)
    {
        if(s[i]=='(')
        {
            open++;
        }
        else
        {
            close++;
        }
    }
    if(close-open==1)
    {
        reverse(s.begin(),s.end());
        for(int i=0; i<s.size(); i++)
        {
            if(s[i]=='(')
            {
                s[i]=')';
            }
            else
            {
                s[i]='(';
            }
        }
    }
    int index=-1;
    for(int i=0; i<s.size(); i++)
    {
        if(s[i]=='(')
        {
            a[i+1]=a[i]+1;
        }
        else
        {
            a[i+1]=a[i]-1;
        }
        if(a[i+1]==0)
        {
            index=i;
        }
    }
    int ans=0;
    for(int i=index+1; i<s.size(); i++)
    {
        if(s[i]=='(')
        {
            ans++;
        }
    }
    cout<<ans;
}