D394
このような、文字列を走査しながら条件に合うものを変更し、変更した文字列をまた走査する問題は頻出です。
愚直に走査をすると、文字列を更新した数だけ文字列を走査することになり計算量がオーバーします。
今回の解法
そこで今回はStackを使います。
カッコを閉じる系の文字が来たときに、直前の文字がそのカッコと対応していれば、消すことができます。直近の文字をStackに入れて、ペアが揃った時に消すことで走査し終わった時にStackが空だったらYesとすることができます。
Stackの使い方
スタックは最後に入れたものを最初に取り出します。いわゆるLIFOです。
FIFOであるキューの使い方はキューの使い方はこちらで解説しています。
stack.add()でもstack.push()と内部的には同じ動きをしますが、addは継承元のメソッドなので基本的には使いません。
ArrayListなどと同じでプリミティブ型は入れれないことに注意してください。
Queueの使い方
