백준 9012번 괄호 (C++)

solved.ac 티어 : 실버 4

문제 유형 : 자료 구조, 스택, 문자열

문제 해결 소감 : 스택으로 이걸 어떻게 풀지 몰라서 종만북에 있는 같은 유형 문제의 해결 아이디어를 참고했다. 아이디어를 아니까 바로 풀렸다. 배우는 과정에서 푸는 거니까 생각이 안나면 이렇게 빨리 빨리 넘어가는게 맞는 것 같다.

문제 해결 전략 : 스택을 이용해서 풀었다. 먼저 스트링 변수에 문자열을 입력한다. 첫번째 문자열 요소부터 순회를 한다. 순회하면서 요소가 ( 이라면 스택에 넣는다. ) 이라면 괄호가 성립하니까 한번 pop한다 이를 반복해서 스택이 비었으면 YES 아니면 NO를 출력하게 했다. 여기서 한 가지 경우가 더 있는데 스택이 비었는데 )를 읽으면 NO이고 바로 다음 문자열로 넘어가게 하면된다. 

스택을 사용하는 이유 :  성립된 괄호를 계속 없애는 식으로 할 때 후입선출 구조인 스택이 도움을 준다.

#include <iostream>
#include <stack>
#include <string>
int t = 0;
std::string str;
std::stack<char> sta;
int cnt = 0;

int main(void) {
  std::cin >> t;
  for (int l = 0; l < t; ++l) {
    std::cin >> str;
    for (unsigned int i = 0; i < str.size(); ++i) {
      if (str[i] == '(') {
        sta.push('(');
      } else if (sta.empty() == false && str[i] == ')') {
        sta.pop();
      } else if (sta.empty() == true && str[i] == ')') {
        std::cout << "NO" << '\n';
        cnt = 1;
        break;
      }
    }
    if (sta.empty() == true && cnt == 0) {
      std::cout << "YES" << '\n';
    }
    if (sta.empty() == false && cnt == 0) std::cout << "NO" << '\n';
    while (!sta.empty()) {
      sta.pop();
    }
    str.clear();
    cnt = 0;
  }
  return 0;
}