괄호 검사는 대표적인 stack을 활용해서 풀이하는 문제이다.

(는 stack에 저장해두고 )를 만나면 stack이 비어있지 않은 경우(=stack에 (가 존재하는 경우) pop() 해주면된다.

그렇게해서 최종 stack이 비어있으면 올바른 괄호이고, stack이 비어있지 않으면 올바르지 않은 괄호이다.

1. 풀이

#include <bits/stdc++.h>
                        
using namespace std;
               
int main() {
    string s;
    int T;
    cin >> T;
    while(T--) {
        stack<char> st;
        cin >> s;
        for(char c:s) {
            if(c=='(') st.push(c);
            else if(!st.empty()) st.pop();
            else {
                st.push(c); break;
            }
        }
        if(st.size()) cout << "NO\n";
        else cout << "YES\n";
    }
    return 0;
}

2. 오답노트

(1) stack 관련 함수 까먹지말자

stack<int> st; //stack 선언 -> 비어있는 stack이 생성됨
st.pop();//stack의 top에 위차한 요소 삭제
st.push(); //stack 요소 삽입(top에 위치하게됨)
st.empty(); //stack이 비어있으면 1을 반환
st.size(); //stack의 size 반환

stack은 지역 변수와 다르게 함수내에서 선언해도 비어있는 상태로 초기화된다.

(2) 로직

처음에는 )를 만나면 stack의 top이 (인지를 확인하고 st.pop()을 수행했다.

그러나 stack에는 항상 (만 넣으므로 top이 (인지 확인할 필요 없이 stack이 empty가 아닌지만 확인해주면된다.

만약 stack이 empty인데 )를 만나면 올바르지 않은 괄호이므로 stack에 push후 바로 break 한다.