AtCoder ABC 064 D - Insertion (緑色, 400 点)

教育的典型題

問題へのリンク

問題概要

カッコ列が与えられる。カッコ列に最小個数の '(' と ')' を挿入して「整合のとれたカッコ列」にせよ。またそのようなものが複数通り考えられる場合には、辞書順最小のものを求めよ。

制約

• 

考えたこと

超定番。

• AtCoder AGC 005 A - STring (300 点)

と大体一緒。以下のようなコードでできる。

#include <iostream>
#include <string>
using namespace std;

int main() {
    int N; cin >> N;
    string S; cin >> S;

    int need_left = 0;
    int pointer = 0;
    for (int i = 0; i < S.size(); ++i) {
        if (S[i] == '(') ++pointer;
        else {
            if (pointer == 0) ++need_left;
            else --pointer;
        }
    }
    int need_right = pointer;

    string res = "";
    for (int i = 0; i < need_left; ++i) res += '(';
    res += S;
    for (int i = 0; i < need_right; ++i) res += ')';
    cout << res << endl;
}