[BOJ] 4949: 균형잡힌 세상

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

 

 

 

 

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

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

  while (true) {
    getline(cin, str);
    if (str == ".") break;
    stack<char> s;
    bool valid = true;
    for (char c : str) {
      if (c == '(' || c == '[')
        s.push(c);
      else if (c == ')') {
        if (s.empty() || s.top() != '(') {
          valid = false;
          break;
        }
        s.pop();
      } else if (c == ']') {
        if (s.empty() || s.top() != '[') {
          valid = false;
          break;
        }
        s.pop();
      }
    }
    if (!s.empty()) valid = false;
    if (valid)
      cout << "yes" << '\n';
    else
      cout << "no" << '\n';
  }
}

다른 문자들은 모두 무시하고 괄호 쌍이 맞는지만 확인하면 되는 문제다.

괄호 쌍은 스택을 사용해서 확인해볼 수 있다.

 

열린 괄호는 무조건 스택에 넣는다.

닫힌 괄호는 스택의 top과 비교해서 짝이 맞으면 pop연산을 수행하면 된다.

이때 만약 짝이 맞지 않거나 스택이 empty인 경우 괄호쌍이 맞지 않다는 뜻이다.

 

문자를 하나씩 꺼내어 모든 처리가 끝났을 때 스택이 empty라면 모든 괄호가 짝이 맞아 pop이 되었다는 의미이고,

empty가 아니라면 짝이 맞지 않아 pop이 되지 못한 괄호가 남아 있다는 뜻이다.

 

위 내용에 맞게 코드를 작성하기 위해 먼저 괄호쌍이 맞는지를 확인할 수 있는 변수 valid를 선언하고,

괄호쌍을 맞추는 로직에서 스택이 empty이거나 짝이 맞지 않으면 valid를 false로 바꾼 후 반복문을 종료했다.

반복문 밖에서 스택이 empty가 아닐 때도 역시 valid를 false로 바꿔줬다.

이제 valid의 값에 따라 "yes"와 "no"를 출력하게 된다.