[백준 / BOJ] C++ 15926 현욱은 괄호왕이야!!

15926번: 현욱은 괄호왕이야!!

 

문제

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

15926번: 현욱은 괄호왕이야!!

 

 

풀이

흔한 괄호 문제의 심화 버전으로 가장 긴 괄호 부분 문자열의 길이를 구하는 문제다. 여전히 스택을 사용해 풀 수 있다.

 

스택의 top의 문자가 '('이고 현재 문자가 ')'라면 top원소를 pop 해준다. 이외의 경우에는 스택에 문자와 문자의 인덱스를 pair로 쌓는다. 이 과정이 모두 끝나고 나면 올바른 괄호 문자열을 이루지 못한 문자만 남게 된다. 이때 스택에 남은 원소 간 인덱스의 차를 이용해 가장 긴 올바른 괄호 문자열의 길이를 구할 수 있다. 그리고 가장 마지막에 남은 원소도 비교해 주기 위해 맨 처음에 인덱스를 -1로 가지는 더미 원소를 하나 넣어준다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, ans = 0;
  string str;
  stack<pair<char, int>> s;
  cin >> n >> str;
  s.push({' ', -1});
  for (int i = 0; i < n; i++)
    if (str[i] == ')' && s.top().first == '(')
      s.pop();
    else
      s.push({str[i], i});
  int a = n;
  while (!s.empty()) {
    int b = s.top().second;
    s.pop();
    ans = max(ans, a - b - 1);
    a = b;
  }
  cout << ans;
  return 0;
}