균형잡힌 세상 — 스택으로 괄호 검사 (BOJ 4949)

아이디어

• 한 줄씩 읽어서 .이면 종료.
• (, [는 스택에 push.
• ), ]를 만나면 스택 top이 각각 (, [인지 확인 후 pop. 아니면 실패.
• 끝났을 때 에러가 있거나 스택에 뭐가 남아 있으면 no, 아니면 yes.

복잡도

• 각 줄 길이를 L이라 하면 O(L).

코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    string str = "";
    while (true) {
        bool err = false;
        stack<char> st;

        getline(cin, str);
        if (str == ".") {
            break;
        }

        for (int i = 0; i < str.length(); i++) {
            if (str[i] == '[') {
                st.push('[');
            }
            else if (str[i] == '(') {
                st.push('(');
            }
            else if (str[i] == ')') {
                if (st.empty() || st.top() != '(') {
                    err = true;
                    break;
                }
                else {
                    st.pop();
                }
            }
            else if (str[i] == ']') {
                if (st.empty() || st.top() != '[') {
                    err = true;
                    break;
                }
                else {
                    st.pop();
                }
            }
        }
        if (err || !st.empty()) {
            cout << "no\n";
        }
        else {
            cout << "yes\n";
        }
    }

    return 0;
}

메모

• 다른 문자들은 전부 무시하므로 그대로 두면 됩니다.
• 입력 줄 끝의 점(.)은 프로그램 종료 트리거이고, 판별용 문자가 아닙니다.