https://www.acmicpc.net/problem/9012

문제

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

예를 들어 (())() 와 ((())) 는 VPS 이지만 (()(, (())())) , 그리고 (() 는 모두 VPS 가 아닌 문자열이다.

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

문제 접근 방법

1. 전체 길이가 홀수이거나 첫 번째 괄호가 닫힌 괄호이면 NO
2. 반복문으로 vps 문자열을 처음부터 순회한다
3. 열린 괄호인 경우 스택에 push
4. 닫힌 괄호인 경우
   1. 스택이 비어있으면 짝이 없으므로 NO
   2. 비어있지 않으면 pop
5. 3,4번을 반복
6. 순회가 끝났을 때
   1. 스택이 비어있으면 YES
   2. 비어있지 않으면 NO

C++ 코드

1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5  int t;
6  cin >> t;
7  while(t--) {
8    string s;
9    cin >> s;
10    if((s.size()&1)==1 || s[0]==')') {
11      cout << "NO" << endl;
12    } else {
13      stack<char> stk;
14      for(int i=0; i<s.size(); ++i) {
15        if(s[i] == '(') stk.push(s[i]);
16        else {
17          if(stk.empty()) {
18            stk.push('X');
19            break;
20          } else {
21            stk.pop();
22          }
23        }
24      }
25      
26      if(stk.empty()) cout << "YES" << endl;
27      else cout << "NO" << endl;
28    }
29  }
30  return 0;
31}

시간 복잡도

• vps 문자열을 순회 - O(S), S = 문자열의 길이
• 괄호를 확인하고 push/pop하는 연산 - O(1)
• 최종 시간 복잡도: O(S)

공간 복잡도

• 문자열 길이가 S이고, S가 전부 열린 괄호일 경우 stack에 전부 push 하므로 - O(S)
• 최종 공간 복잡도: O(S)