백준 #9012번 괄호 c++

 

백준 9012번 괄호 문제이다. 실버4의 문제.

 

스택의 활용 정도 되는 문제이다.  

 

스택의 기본구조인 선입후출의 개념과 stack.empty(), stack.top() 등의 개념을 활용하여 풀 수 있는 문제이다.

 

이 문제의 핵심은 닫는 괄호 ')' 의 짝이 있는가를 찾는 것이다.

 

처음부터 닫는 괄호가 들어오면 당연히 NO를 반환해야 하는것이고

 

닫는 괄호와 여는 괄호의 갯수가 같아도, 짝이 맞지 않으면 해결할 수 없다.

 

아래의 코드를 살펴보자.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    int testcase;
    cin >> testcase; // 몇 번 돌지 입력받음
   
    while(testcase--) {
        stack<char> st;
        string s;
        cin >> s; // 괄호들을 문자열로 입력
        
        for(int j = 0; j < s.length(); j++) {
            if(st.empty()) { //스택이 비어있다면 push
                st.push(s[j]);
            }
            else { //스택이 비어있지 않고
                if(st.top() == '(' && s[j] == ')') { //top이 여는 괄호면서 다음 인자가 닫는 괄호면
                    st.pop();//Pop
                }
                else {//그 외의 경우는 모두 push
                    st.push(s[j]);
                }
            }
        }
        if(st.empty()) {
            cout << "YES" << "\n";
        }
        else {
            cout << "NO" << "\n";
        }
    }
}

 

 

 

풀이의 핵심은 stack.top()  == '(' 면서 s[j] == ')'를 확인하는데 있다.

 

그후 pop을 하고 작업이 완료되었음에도 스택에 남는 괄호가 있다면

 

괄호의 짝이 맞지 않는 것이기 때문에 NO를 출력한다.