[알고리즘] 9012번: 괄호

0. 문제

 

9012번: 괄호

 

---

1. 문제 이해

 

올바른 괄호 문자열인지 판단하여 YES나 NO를 출력하는 문제다.

1. 올바른 괄호 문자열인지 판단하는 방법은 Stack을 활용하면 좋겠다.
2. 여는 괄호 (는 스택에 저장한다.
3. 닫는 괄호 )는 스택의 최상위 (를 삭제한다.
4. 모든 문자에 대하여 실행했을 때 스택이 비어있다면 Yes 아니면 NO

 

---

2. 제출

 

//백준 9012번: 괄호
#include <iostream>
#include <stack>

using namespace std;

stack<char> stk;
int n;

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

  cin >> n;
  for(int tc=1; tc<=n; tc++){
    while(stk.size()){
      stk.pop();
    }

    bool underflow = false;
    string str ="";
    cin >> str;

    for(char c : str){
      if(c=='(')stk.push('(');
      if(c==')'){
        if(stk.size())
          stk.pop();
        else{
          underflow = true;
          break;
        }
      }
    }

    if(underflow){
      cout << "NO" << "\n";
      continue;
    }
    if(stk.size())
      cout << "NO" << "\n";
    else
      cout << "YES" << "\n";
  }

  return 0;
}

(는 스택에 푸시하고 )는 팝한다.

 

    while(stk.size()){
      stk.pop();
    }

모든 테스트케이스를 시작할 때 스택을 초기화한다.

 

if(c==')'){
  if(stk.size())
    stk.pop();
  else{
    underflow = true;
    break;
  }
}

pop()할 때는 스택 언더플로우를 검사한다.

 

---

3. 더 좋은 코드

// 백준 9012번: 괄호
#include <iostream>
#include <stack>
using namespace std;

int n;
string s;

bool check(string s){
  stack<char> stk;
  for(char c : s){
    if(c == '(')stk.push(c);
    else{
      if(!stk.empty()) stk.pop();
      else return false;
    }
  }
  return stk.empty();
}

int main(){
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> s;
    if(check(s)) cout << "YES\n";
    else cout << "NO\n";
  }
  return 0;
}

2중 for문일 때 두 for문 간에 연관성이 적다면 내부의 for문을 함수로 빼내는 방법이 도움이 된다.

 

---