与えられた文字列が「悪い」かどうかを判定するC++プログラム

問題概要

n 文字からなる文字列 S が与えられます。S には小文字の英字と「)」という文字が含まれています。この文字列が悪い(bad)と判定されるのは、末尾に連続する「)」の数が、それ以外の残りの文字数よりも厳密に多い場合です。ここでは、与えられた文字列 S が悪いかどうかをチェックするプログラムを作成します。

たとえば、入力が S = "fega))))))" の場合、出力は True になります。なぜなら、この文字列には英字が4文字しかないのに対し、「)」が6個あるためです。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

1. カウンタ変数 ans を 0 で初期化します。
2. 文字列の長さを n とし、インデックス i を末尾( n - 1 )からスタートさせます。
3. i が 0 以上で、かつ S[i] が「)」である限り、i を減らしていきます。これにより、末尾に連続する「)」の個数を特定できます。
4. 末尾の「)」の数を z = n - 1 - i として計算します。
5. ans = 2 * z - n を計算します。この値が正であれば、「)」の数がそれ以外の文字数を上回っていることを意味します。
6. ans > 0 なら true を返し、そうでなければ false を返します。

C++による実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

bool solve(string S) {
    int ans = 0;
    int n = S.size();
    int i = n - 1;
    while (i >= 0 && S[i] == ')')
        i--;
    int z = n - 1 - i;
    ans = 2 * z - n;
    if (ans > 0)
        return true;
    else
        return false;
}
int main() {
    string S = "fega))))))";
    cout << solve(S) << endl;
}

実行結果

入力:

"fega))))))"

出力:

1

出力が「1」となるのは、関数 solve() が true を返したことを意味します。つまり、文字列「fega))))))」は悪い(bad)文字列であると正しく判定されました。

計算量について

このアルゴリズムは、文字列を一度だけ後ろから走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) となります。非常にシンプルかつ効率的な解法と言えるでしょう。