ABC-064-D Insertion

■■■問題■■■

(と)で構成されるN文字の文字列Sが与えられる。
Sにいくつかの(または)を挿入することで正しい括弧列を作りたい。

ただし、正しい括弧列は次のように定義されている：
●()は正しい括弧列である
●Xが正しい括弧列であるとき、(X)は正しい括弧列である
●X、Yが正しい括弧列であるとき、XYは正しい括弧列である
●それ以外の括弧列は正しくない

そのとき、作れる最も文字数が少ない正しい括弧列を求めなさい。
このようなものが複数ある場合は、辞書順最小のものを求めなさい。

■■■入力■■■

N
S

●Sの長さはNである
●1 <= N <= 100
●Sは(と)のみで構成されている

■■■出力■■■

Sから(、)を挿入していったときに作れる最小の長さの正しい括弧列のなかで辞書順最小の文字列を出力しなさい。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("())");
            //(())
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            WillReturn.Add(")))())");
            //(((()))())
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8");
            WillReturn.Add("))))((((");
            //(((())))(((())))
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[1];

        int PutFirst = 0;
        int StackCnt = 0;
        foreach (char EachChar in S) {
            if (EachChar == '(') {
                StackCnt++;
            }
            if (EachChar == ')') {
                if (StackCnt == 0) PutFirst++;
                else StackCnt--;
            }
        }

        var Answer = new System.Text.StringBuilder();
        if (PutFirst > 0) Answer.Append(new string('(', PutFirst));
        Answer.Append(S);
        if (StackCnt > 0) Answer.Append(new string(')', StackCnt));
        Console.WriteLine(Answer.ToString());
    }
}

解説

開き括弧をS、閉じ括弧をEとして、

  SEEESSS
にSまたはEを追加した括弧列で、
最小文字列で辞書順最小な文字列は、下記となります。(追加文字を赤色で表示)
SSSEEESSSEEE

これは、下記のアルゴリズムで実現できます。

●対となるSがないEは、左端にSを追加する。
●対となるEがないSは、右端にEを追加する。

最小の文字数なので余計なS、Eは追加できなくて、
辞書順で最小としたいので、Sを左端、Eを右端に追加するのが最適だからです。