SRM521 Div1 Easy - MissingParentheses
問題
以下のどれかを満たす文字列を良い括弧列と定義する
1) 空文字列
2) ある良い括弧列を()で囲んだもの
3) 2つの良い括弧列を並べて繋げたもの
与えられる文字列sを良い括弧列にするために追加する必要のある括弧の最小値を求める
解法
sを左から見ていき、今までに見た '(' の個数を ')' の個数が上回ったとき、sのそれ以降がどんな並びであっても "sの左端からそこまでの部分" が自然に良い括弧列になることはないので、絶対に '(' を補ってやる必要がある
これを繰り返すのが最善
実装
最後に余った '(' の数だけ ')' を補うのも忘れずに
class MissingParentheses { public: int countCorrections(string s) { int a = 0, res = 0; each(i,s) { if (i=='(') a++; else { if (a==0) res++; else a--; } } return res+a; } };