[BOJ] 4949 균형잡힌 세상

이 문제는 사실 군대에서 한 번 풀었었던 문제다. 스택에 여는 괄호는 무조건 push, 닫는 괄호가 나올 때 top과 짝이 맞으면 넘어가고 짝이 맞지 않거나 스택이 비었으면 no를 출력하는 간단한 문제다.

 

 다만 군대에서 풀었을 때 TLE가 발생했는데 그 이유는 초기화의 문제였다. 이 문제는 C++로 풀었는데, 만약 C로 풀었다면 그냥 top = -1을 대입하면 빠르게 초기화할 수 있었겠지만 stl을 사용하다보니 초기화 방법이 다음과 같이 할 수밖에 없었다.

void init() {
  if(s.empty()) return;
  while(!s.empty()) s.pop();
}

그런데 정말 간단한 방법을 찾았다.

 

"."이 입력될 때까지 무한루프고, 어차피 한 줄씩 입력받으면서 바로 결과값을 출력한다면 그냥 매 루프마다 스택을 새로 선언하면 되지 않을까?

 

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    while(1) {
        string temp;
        getline(cin, temp);
        if(temp.length() && temp[0] == '.') break;

        stack<char> s;
        bool res = true;
       
        for(int i = 0; i < temp.length(); i++) {
            if(temp[i] == '(' || temp[i] == '[')
                s.push(temp[i]);
            else if(temp[i] == ')') {
                if(!s.empty() && s.top() == '(') s.pop();
                else {
                    res = false;
                    break;    
                }
            } else if(temp[i] == ']') {
                if(!s.empty() && s.top() == '[') s.pop();
                else {
                    res = false;
                    break;    
                }
            }
        }
        if(res && s.empty()) cout << "yes\n";
        else cout << "no\n";
    } 

    return 0;
}

그 결과는 성공이였다.