9012

들어가는 말

괄호가 올바른지 확인하는 문제로 스택을 이용하면 간단하게 풀 수 있었다. 그러나... 분명 맞게 푼 거 같은데 자꾸만 런타임 에러가 나는 거 아닌가. 고치고 또 고쳐도 런타임 에러는 계속 났다. 도대체 왜?! 그러다가 대단한 실수를 발견했으니... 바로 string s = 0이라고 해놓은 것. 아니, 왜 문자열을 초기화하는데 0을 넣은 거지? 정수형도 아니고 ""도 아니고... 요즘 많이 피곤한 가? 아무튼 그래서 이렇게 시간 쓸 문제 아니었는데 어이없는 이유로 시간을 썼다. ㅎㅎ.

코드 설명

sol 함수를 따로 지정해서 참이면 YES를 거짓이면 NO를 반환하게 했다.

sol 함수는 문자열을 처음부터 끝까지 돌려주는데, 만일 열린 괄호라면 스택에 넣어두고 닫힌 괄호라면 스택이 비어있는지 아닌지를 확인해준다. 스택이 비어있으면 이는 열린 괄호가 없다는 뜻, 즉 올바르지 않은 괄호라는 의미(닫힌 괄호가 먼저 나오면 올바르지 않다)이므로 false를 반환한다. 만일 스택이 비어있지 않다면 가장 최근에 넣었던 열린 괄호를 pop한다.

for문을 전부 돌린 후에는 스택에 문자가 있는지를 검사한다. 스택이 문자가 있다면 이는 올바르지 않은 괄호(열린 괄호가 있는데 닫힌 괄호가 없으므로)이므로 false를 반환한다. 아니라면 true를 반환한다.

코드

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

using namespace std;

bool sol(string str){
    stack<char> st;
    
    for(int i=0; i<str.length(); i++){
        if(str[i] == '('){
            st.push(str[i]);
        }else{
            if(st.empty()){
                return false;                
            }else{
                st.pop();
            }
        }
    }
    
    if(st.empty()){
        return true;
    }else{
        return false;
    }

}

int main(void){
    int cnt = 0;
    cin >> cnt;
    
    for(int i=0; i<cnt; i++){
        string s;
        cin >> s;
        
        if(sol(s)){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
    
    return 0;
}