[c++] 백준 4949번: 균형잡힌 세상

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

4949번: 균형잡힌 세상

풀이

스택을 이용해 푸는 문제. 9012번과 비슷해서 쉽게 풀릴 줄 알았는데 괄호의 종류가 많아지면서 풀이할 때 헤맸다. 괄호가 (소괄호)와 [대괄호] 두 종류이니 스택도 두 개 필요하겠지라고 단순히 생각했다가 한참 헤맸다.

 

입력받은 한 문장을 for문으로 읽어들이며 (, ), [, ] 네 가지 문자를 만날 때 마다 적절한 조건을 걸어 스택에 넣거나 빼주면 된다.

(와 [의 경우 추가 조건 없이 스택에 push해준다. 단, ( ]와 같이 짝지어질 경우 틀린 것이므로 두 괄호의 종류를 구분하여 push한다.

)와 ]는 각각 (, ]와 짝을 이루면 pop해서 스택에서 제거한다.

 

"yes"를 출력하기 위해서는 입력받은 한 문장을 for문을 돌며 끝까지 읽어야하기 때문에, "no"를 출력하는 경우를 먼저 찾아 거른다.

)를 입력받은 경우를 예로 들면, 스택이 비어있거나 스택의 top이 (가 아닌 경우 "no"를 출력하고 for문을 종료하여 다음 새로운 문장을 입력받는다. 위 조건에 걸리지 않고 for문이 종료되어도 스택이 비어있지 않다면 "no"를 출력한다. 위 조건을 모두 만족한 경우 "yes"를 출력한다.

 

코드

#include <iostream>		//getline 함수 (\n까지 문자열 입력 받음)   
#include <stack>
using namespace std;

int main() {
    while (1) {  
        stack<int> st;
        string tmp; getline(cin, tmp);
        if (tmp == ".") return 0;
        int flag = 0;

        for (int i = 0; i < (int)tmp.size(); i++) {
            if (tmp[i] == '(') st.push('(');

            else if (tmp[i] == '[') st.push('[');
        
            else if (tmp[i] == ')') {
                if (st.empty() || st.top() != '(') {    //st가 비어있거나 top이 )일 경우
                    flag = 1;
                    break;
                }
                else if (!st.empty() && st.top() == '(') st.pop();
            }

            else if (tmp[i] == ']') {
                if (st.empty() || st.top() != '[') {
                    flag = 1;
                    break;
                }
                else if (!st.empty() && st.top() == '[') st.pop();
            }
        }
        if (flag) printf("%s\n", "no");
        else if (st.size()) printf("%s\n", "no");
        else printf("%s\n", "yes");
    }
}