[11899번] 괄호 끼워넣기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Stack 

스택을 이용하는 가장 기본적인 문제이다. 스택을 알고있지 않다면, 배열로 해결하기 조금 까다롭거나,

다른 수학적 방법을 고안해야 하는 문제이다.

스택의 관점은 다음과 같다.

'('가 들어오고 그다음 ')'가 들어올 때,

')'를 pop하고, 그다음 스택의 top가 '('인지 확인한다. 

이때 top이 '('면 마저 pop하고 ')'면 다시 이전에 pop한 ')'를 push해준다.

ex ::

() -> ( -> Empty :: (pop -> pop)

)) -> ) -> )) :: (pop -> push again)

소스 코드 : 

#include <iostream>
#include <string.h>
#include <stack>
 
using namespace std;
 
int main()
{
    stack<char> s;
 
    char arr[60];
    int len;
 
    cin >> arr;
 
    len = strlen(arr);
    
    s.push(arr[0]);
    
    for (int i = 1; i < len; i++)
    {
        s.push(arr[i]);
 
        if (s.top() == ')')
        {
            s.pop();
            
            // s.size() != 0은 ()) << 같은 경우 방지
            if (s.size() != 0 && s.top() == '(')
                s.pop();
            
            else
                s.push(')');
        }
    }
    cout << s.size();
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>