C++で括弧のバランスを取るために必要なコストを求める方法

このチュートリアルでは、括弧のバランスを取るために必要なコスト(最小移動回数)を求めるプログラムをC++で解説します。

問題設定は次のとおりです。開き括弧「(」と閉じ括弧「)」からなる文字列が与えられ、括弧の位置を1つ移動するたびにコストが1かかるとします。このとき、文字列全体の括弧のバランスを取るために必要な最小コストを求めます。開き括弧と閉じ括弧の個数が一致しないなど、バランスを取ることが不可能な場合は -1 を出力します。

アルゴリズムの考え方

この問題は、累積和(プレフィックスサム)を使うことで効率的に解くことができます。手順は以下のとおりです。

1. まず、開き括弧「(」と閉じ括弧「)」の個数をそれぞれ数えます。両者の数が一致しない場合は、どれだけ移動してもバランスを取れないため -1 を返します。
2. 次に、文字列を先頭から走査し、「(」なら +1、「)」なら -1 として累積値を計算していきます。
3. 累積値が負になった時点で、対応する開き括弧が不足していることを意味します。そこで、その累積値の絶対値をコストとして加算します。

この「累積値が負になった箇所の絶対値の総和」が、括弧を移動してバランスを取るために必要な最小コストとなります。

実装例

#include <bits/stdc++.h>
using namespace std;
int costToBalance(string s) {
    if (s.length() == 0)
        cout << 0 << endl;
    //開き括弧と閉じ括弧の個数を記録
    int ans = 0;
    int o = 0, c = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(')
            o++;
        if (s[i] == ')')
            c++;
    }
    if (o != c)
        return -1;
    int a[s.size()];
    if (s[0] == '(')
        a[0] = 1;
    else
        a[0] = -1;
    if (a[0] < 0)
        ans += abs(a[0]);
    for (int i = 1; i < s.length(); i++) {
        if (s[i] == '(')
            a[i] = a[i - 1] + 1;
        else
            a[i] = a[i - 1] - 1;
        if (a[i] < 0)
            ans += abs(a[i]);
    }
    return ans;
}
int main(){
    string s;
    s = ")))(((";
    cout << costToBalance(s) << endl;
    s = "))((";
    cout << costToBalance(s) << endl;
    return 0;
}

実行結果

9
4

出力の解説

1つ目の入力「)))(((」の場合、出力は 9 となります。先頭から累積値を計算すると -1、-2、-3、-2、-1、0 と推移し、負の値の絶対値を合計すると 1+2+3+2+1=9 となります。

2つ目の入力「))((」の場合、出力は 4 となります。累積値は -1、-2、-1、0 と推移し、負の値の絶対値の合計は 1+2+1=4 です。

このアルゴリズムは文字列を一度走査するだけで済むため、計算量は O(n) と非常に効率的です。累積和による括弧の深さの管理は、「有効な括弧列の判定」や「最長の有効な括弧部分列を求める」など、括弧に関するさまざまな問題に応用できる重要なテクニックです。