9012번 : 괄호

이 문제는 사실 예전에 본적이 있다.

먼 과거긴 하지만 수많은 노가다를 통해 일종의 인식기를 만들어서 풀었고 심지어 답도 맞췄다.

요즘 말로하면 "어케 맞췄노" 정도 되겠다.

 

각설하고 문제를 분석하면, 쉽게 말해 Stack을 통한 인식기를 만들라는 것이다.

원리는 간단하다.  "("가 나오면 push하고 ")"가 나오면 pop한다.

몇 번째 "("가 ")"와 짝인진 사실 알기 힘들다. 하지만 명백한 사실은, 스택에 "(" 가 남아있다면 ")"이 부족하단 것이다.

 

단, 낮은 정답률에서 알 수 있다시피 그게 다가 아니다. 조심해야할 예외가 있다.

 

코드는 아래와 같다.

 

#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
int main(int argc, char *argv[])
{
    int T;
    cin>>T;
    
    stack<char> stk;
    string op;
    bool vps = true;
 
    for (int i=0; i<T; i++)
    {
        cin>>op;
        vps = true;
        for (int j=0; j<op.length(); j++) {
            if(op[j] == '(')
                stk.push(op[j]);
            else
            {
                if(!stk.empty())
                {
                    stk.pop();
                }
                else
                    vps = false;
            }
        }
        if(stk.empty() && vps) cout<<"YES"<<endl;
        else            cout<<"NO"<<endl;
        
        while(!stk.empty()) stk.pop();
    }
    
    return 0;
}