きままにものづくり

日々の気付いたことなんかを書いてます。

SRM628Div2Medium

問題

長さNの文字列が与えられる。文字列の要素は(,),{,},[,]の6文字かどの文字にもなれる'X'のどれかである。全ての括弧が対応しているかを確認せよ。ある括弧をまたいで対応している場合は、無効とする。(例: ([)])

解法

ひとつのスタックを用いることで、対応しているかどうかの確認はできる。
Xの数は最大でも5個しか含まれないので全探索をする。

計算量

対応確認:O(N)
Xの探索: 6^X
全体: O(N6^X)

コード