괄호

시간 제한1초메모리 제한128 MB

요약

괄호 문자열이 주어질 때, 부분 수열로 얻을 수 있는 정규 괄호 수열의 최대 길이를 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 구간, 스택
정답자: 아직 제출이 없습니다

문제

올바른 괄호 수열을 다음과 같이 귀납적으로 정의한다.

빈 수열은 올바른 괄호 수열이다.
$s$ 가 올바른 괄호 수열이면 $(s)$ 와 $[s]$ 도 올바른 괄호 수열이다.
$a$ 와 $b$ 가 올바른 괄호 수열이면 이 둘을 이어 붙인 $ab$ 도 올바른 괄호 수열이다.
위 규칙으로 만들 수 없는 수열은 올바른 괄호 수열이 아니다.

예를 들어 다음 수열은 모두 올바른 괄호 수열이다.

(), [], (()), ()[], ()[()]

반면 다음 수열은 올바른 괄호 수열이 아니다.

(, ], )(, ([)], ([(]

괄호 문자로 이루어진 수열 $a_1 a_2 \dots a_n$ 이 주어질 때, 이 수열의 부분수열 중 올바른 괄호 수열이 되는 가장 긴 것의 길이를 구하라. 즉, $1 \le i_1 < i_2 < \dots < i_m \le n$ 인 인덱스 $i_1, i_2, \dots, i_m$ 에 대하여 $a_{i_1} a_{i_2} \dots a_{i_m}$ 이 올바른 괄호 수열이 되는 가장 큰 $m$ 을 구하면 된다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 문자 (, ), [, ]만으로 이루어진 한 줄이며, 각 줄의 길이는 $1$ 이상 $100$ 이하이다.

입력의 끝은 end라는 단어 하나만 있는 줄로 표시하며, 이 줄은 처리하지 않는다.

출력

각 테스트 케이스마다 가장 긴 올바른 괄호 부분수열의 길이를 한 줄에 하나씩 출력한다.

힌트

수열 ([([]])]의 경우, 가장 긴 올바른 괄호 부분수열 중 하나는 [([])]이며 그 길이는 $6$ 이다.

예제2

예제 1

입력

((()))
()()()
([]])
)[)(
([][][)
end

예상 출력

예제 2
입력
```
()
[]
end
```
예상 출력
```
2
2
```