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

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

substring이 아닌, 그냥 주어진 괄호쌍 전체가 올바른 괄호쌍인지 확인하는 문제는 굉장히 익숙할 것입니다. 이제 substring에 대해서 생각해보면, 특정 시작점 i에서 진행할 때 최대한 올바른 괄호쌍을 늘이려면 어떻게 해야하는지를 생각해봅시다.

예제로 주어진 ( ( ) ) ( 에 대해, ( 는 +1, )는 -1을 부여해보면 0 1 2 1 0 1 이라는 값을 얻을 수 있습니다. 우리는 이 때 0 1 2 1 0이 최대 구간이 되고 1 2 1 0 1은 최대 구간이 될 수 없음을 알 수 있는데, 1 2 1 0 1은 시작점 1보다 낮아진 값(0)이 등장했기 떄문입니다.

이제 문자를 하나씩 보면서 진행합니다. 진행하면서 현재의 값을 index로 저장합니다. 그리고 )이 나오면 바로 직전에 저장한 index를 제거합니다.

초기값 : val 0 -> index 0

(

val 0 -> index 0

val 1 -> index 1

( (

val 0 -> index 0

val 1 -> index 1

val 2 -> index 2

( ( )

val 0 -> index 0

val 1 -> index 1. 현재 index가 3이고 val이 1이므로 3-1 = 2를 최댓값에 저장

( ( ) )

val 0 -> index 0. 현재 index가 4이고 val이 0이므로 4-0 = 4를 최댓값에 저장

( ( ) ) )

val -1 -> index 5.

뭐 이런식으로요. 설명이 쉽지않네요 ㅠ_ㅠ

https://github.com/blisstoner/BOJ/blob/master/15926.cpp