No.064 D

カウンタを用意して文字列を最初から見ていき,

  • ( ならカウンタを1増やす.
  • ) ならカウンタを1減らす. カウンタがマイナスになった場合は ( が足りないということなので, カウンタをリセットし, 文字列の先頭に ( を追加する. (先頭に追加するのが辞書順で最も早くなる)

を繰り返す. 最後まで見たときにカウンタが1以上なら ) が足りないということなので, 文字列の末尾にカウンタの数だけ ) を追加する. (末尾に追加するのが辞書順で最も早くなる)