SRM 521 DIV1 Easy - MissingParentheses

SRM 521 DIV1 Easy - MissingParentheses

8:27

問題


http://community.topcoder.com/stat?c=problem_statement&pm=10943&rd=14546

カッコの並びが与えられる。
カッコがきちんと閉じた形になるために、追加で必要なカッコの数を求める。

解き方


左カッコが出てきたら＋１、右カッコが出てきたらー１としてカッコの閉じ具合を走査する。
０から始め、マイナスになるときは必ず左にカッコが必要なので答えを＋１して数を０に戻す。
そうでない場合はそのまま走査し、最後に残った数を答えに足せばよい。

コード



class MissingParentheses {

public: int countCorrections(string par) {
int left=0,ans=0;

FORE(i,0,par.size()){
if(par[i]=='(')left++;
else if(left>0)left--;
else ans++;
}

return ans+left;
}

};

Share this

Google Facebook Twitter More

Related Posts