(C++) 백준 4949번 - 균형잡힌 세상

문제 링크 : https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

풀이

닫는 괄호들이 나왔을 때 짝이 맞는 괄호가 stack의 Top에 위치해 있다면 이는 균형 잡힌 문장이라고 볼 수 있다는 점이 이 문제 풀이의 핵심 요소이다.

처음에 제출했을 때 실패가 나와서 왜 그런지 생각해 봤더니 "( ) ( ) ["와 같이 열린 괄호가 더 많은 경우여서 애초에 균형이 맞지 않은 것들을 예외 처리하지 못한 것이 원인이었다. 따라서 마지막 출력할 때에 스택이 모두 비었는지 확인하는 것이 필요했다. 

#include <iostream>
#include <stack>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  
    while(1){
        stack<char> S;
        string s;
        getline(cin, s);
        if(s == ".") break; // .가 나오면 break
        bool valid = true;
        for(auto a : s){
            if(a == '(' or a == '[') S.push(a); // 여는 괄호면 stack에 넣기
            else if(a == ')'){ // 닫힌 소괄호면
            	// top에 여는 소괄호가 있고 스택이 비지 않았다면 pop
                if(!S.empty() and S.top() == '(') S.pop();
                else{
                    valid = false; // 그렇지 않으면 valid하지 않음
                    break;
                }
            }else if(a == ']'){
            	// top에 여는 대괄호가 있고 스택이 비지 않았다면 pop
                if(!S.empty() and S.top() == '[') S.pop();
                else{
                    valid = false; // 그렇지 않으면 valid하지 않음
                    break;
                }
            }
        }
        if(S.empty() and valid) cout << "yes" << "\n"; // 스택이 비었고, valid하면 yes
        else cout << "no" << "\n"; // 그렇지 않으면 no
    }
}