括弧列を修正する
文字列
s が与えられ、これは開き括弧と閉じ括弧で構成されています。ここで、開き括弧を閉じ括弧に、あるいは閉じ括弧を開き括弧に変更することが許されています。正しい括弧列を得るために、最小で何回の変更が必要になるでしょうか。入力
入力は1行のみで、文字列
s (1 ≤ |s| ≤ ) が与えられます。文字列 s の長さは偶数であることが保証されています。出力
括弧列を正しくするために必要な変更回数の最小値を出力してください。
Examples
入力 | 出力 |
()(( | 1 |
)( | 2 |
()() | 0 |
((() | 1 |
解説
- ()(( → ()() ⇒ 1回の変更
- )( → () ⇒ 2回の変更
- ()() ⇒ 変更する必要はありません
- ((() → ()() ⇒ 2回の変更
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB