解法
まず、順列に逆の情報を持たせます。すなわち、
番目の開き括弧が
番目の閉じ括弧に対応しているとき、 数列の
番目の値は
である。
というようにします。
すると、スタックを利用して、次のような操作を行うことで、問題の条件を満たす括弧列を作成することができます。
まず、今見ている配列の添え字を、次に出現する閉じ括弧が
番目であるとします。
スタックに
をプッシュします。と同時に、答えとなる文字列
に"("を追加します。
スタックの一番上と、
を比較します。数字が同じであれば、スタックからその数字を取り出して捨てます。そして、
2の操作が行える限り行います。スタックが空になるか、数字が一致しなくなったら1の操作に戻ります。
をすべてプッシュし終えていたら、全ての操作を終了します。
こうしてできたが答えとなります。ただし、スタックの中身が空になっていなければ、問題の条件を満たす文字列が無かったことになり、":("を出力することになります。
感想
括弧列といえばスタックを頭の片隅に入れている気がします。
今回も片隅においてはいたのですが、うまい処理を思いつけずにいたので、先輩にヒントをいただきました。
再帰でやろうとしていたので、こっちの方がおそらくシンプルに実装できたと思います。
