[BOJ 9021] 괄호

문제 출처

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

 

문제 풀이

문자열을 확인하면서 "("인 경우 stack에 push

만약 문자열이 ")"이고 stack이 비어있다면 VPS가 아니라고 판단.

stack이 비어있지 않다면 top에 "("인지 확인한뒤 pop

모든 문자열을 확인한 뒤 stack이 비어있다면 VPS 비어있지 않으면 VPS가 아니라고 판단할 수 있다.

이 문제는 stack이 아닌 카운팅하면서 문제를 풀 수도 있으며 두가지 방법 모두 O(N)의 복잡도를 가진다.

 

소스 코드

//
//  main.cpp
//  BOJ_9012
//
//  Created by sw on 18/12/2019.
//  Copyright © 2019 seungwoo. All rights reserved.
//

#include <iostream>
#include <stack>

using namespace std;
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin>>t;
    
    while (t--) {
        string input;
        cin>>input;
        stack<char> st;
        
        for (int i=0; i<input.size(); i++) {
            if (input[i] == '(') {
                st.push(input[i]);
            } else {
                if (!st.empty() && st.top() == '(') {
                    st.pop();
                } else {
                    st.push(')');
                    break;
                }
            }
    }
        if (st.empty()) cout<<"YES"<<"\n";
        else cout<<"NO"<<"\n";
    }
        
    return 0;
}