백준 9012번 c++

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

9012번: 괄호

stack을 활용하는 문제

#include <iostream>
#include <stack>
using namespace std;
stack <char> s;

int main()
{
    int n;
    string a;
    cin>>n;

    for(int i=0 ; i<n ; i++)
    {
        cin>>a;
        for(int j = 0 ; j<a.length() ; j++){
            if(a[j]=='(')
                s.push('(');
            else if (a[j]==')')
                if(!s.empty() && s.top()=='(')
                    s.pop();
                else
                    s.push(')');
        }

        if(s.empty())
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;

        while(!s.empty())
            s.pop();
    }
}

5달전에 풀다가 묵혀놨는데 지금이 더 못하는 듯;;; ㅠㅠㅠㅠ

 

1차 사고

stack을 활용한다는 건 알고 있어서 무작정 모든 문자열을 stack에 push한 다음 pop을 하면서 짝을 맞추려고 했음

근데 이게 막상 해보려니까 생각보다 까다로움

 

2차 사고 

'(' 이거면 stack에 push ')' 이거면 pop 해서 최종적으로 stack이 비었으면 yes, 아니면 no 출력!

 

 

주의할 점

[1] ')' 이게 왔을 때

앞에가 '(' 이거일 때만 pop을 해야함

for문이 0부터 시작하도록 설정했기 때문에 i-1을 할 때 0이 되면 안 됨 = stack안에 적어도 뭐 하나가 있을 때 pop을 해야함

아니면 push!!

 

[2] stack 초기화 해주기

새로운 string을 받기 전에 stack 초기화를 해줘야함!

stack이 빌 때 까지 pop을 해주면 됨