No.22 括弧の対応

Quiz

https://yukicoder.me/problems/no/22

Submit

https://yukicoder.me/submissions/336370

解法

  • Stackで解いている人が多いけれど、私は別の方法で。
  • K番目が指すのは ( だと仮定する
  • K以降に読み進めながら、(が来たらcount++, )が来たらcount--していき、count==0で止まる
  • そこが対応する括弧の位置
  • これを解く関数 f を作っておく

f:id:peroon:20190409004842j:plain

  • K番目が指すのが ) だった場合、
  • sを反転させ、始点も反転させて解を出す(fを用いる)
  • 最後に解も反転させれば求まる

Stackバージョンでも解いてみた