[Stack] 백준 9012번 - 괄호

 

생각해보기

열린괄호는 stack에 넣다가 닫힌 괄호가 나오면 stack에 열린괄호 있는지 없는지 확인

 

1. '('가 나타나면 모두 stack에 push로 넣어준다

2. ')'가 보이면 stack에 있는 '('을 Pop 시킨다

    만약 이때 stack에 아무것도 없다면 바로 NO

3. input string의 모든 것을 다 보았다면 

    이때의 stack이 empty면 YES

    empty가 아니면 NO

 

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;
#define endl '\n'
#define MAX 1000000

int T;
// int numbers[1025][1025]; 사실상 필요가 없다

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin>>T;

    stack<char> st;
    int i, j;
    string input;
    for(i=0; i<T; i++){
        cin>>input;
        for(j=0; j<input.length(); j++){
            if(input[j]=='(')
                st.push('(');
            else
            {
                if(st.empty()){
                    cout<<"NO"<<endl;
                    break;
                }
                else{
                    st.pop();
                }
            }
            
        }
        if(st.empty() && j==input.length())
            cout<<"YES"<<endl;
        else if(!st.empty() && j==input.length())
        {
            cout<<"NO"<<endl;
        }
        while(!st.empty()){
            st.pop();
        }
    }

}