[백준 9012] 괄호

백준 9012번 - 괄호

백준 9012번

❓ 문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

---

✏️ 풀이

풀 때 애를 좀 먹었던 문제이다.
stack으로 접근하는 방법까진 맞았는데, 구현을 이상하게 해버려서 시간을 많이 잡아먹었다.

괄호의 짝이 맞는지를 묻는 문제이다.
VPS라고 하나보다.몰랐음..

어쨋든, 이 문제의 접근 방식은 스택이고, 문자열을 하나씩 받아들인다.
이 때, 문자열의 0번째 index부터 끝까지 돌면서 스택을 쌓고 빼면서 조건을 체크해가는 식으로 풀면 된다.

조건은 이렇다.

1. 우선, index가 0이거나 '('라면 stack에 push해준다.
2. 그게 아닐 경우, stack이 비었는지 확인을 한다.
3. stack이 empty() 상태가 아닐 경우, stack의 top()이 '('이면서 현재 index가 ')'라면 pop()을 한다.
4. 만약 위 조건에 모두 걸리지 않는다면 예외이므로 return "NO"를 해준다.

이 조건을 가지고 index를 전부 돌면 예외 상황까지 모두 잡을 수 있었다.
stack의 성질과 조금만 생각을 한다면 충분히 풀 수 있는 문제이다.
아래는 정답 코드이다.

---

✔️ 정답 코드

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

vector<string> result;
string VPS_check(string PS);

int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int T;
  cin >> T;

  for (int i=0; i<T; i++) {
    string temp;
    cin >> temp;
    result.push_back(VPS_check(temp));
  }
  for (int i=0; i<T; i++) {
    cout << result[i];
    if (i != T-1)
      cout << "\n";
  }
  return 0;
}

string VPS_check(string PS) {
  stack<char> a;

  for (int i=0; i<PS.length(); i++) {
    if (i == 0 || PS[i] == '(')
      a.push(PS[i]);
    else if (!a.empty()) {
      if (a.top() == '(' && PS[i] == ')') {
        a.pop();      
      }
    }
    else
      return "NO";
  }
  return a.empty() ? "YES" : "NO";
}