C++で2つの0に挟まれた要素を削除する方法をわかりやすく解説

この記事では、「0」と「1」のみで構成される文字列が与えられたとき、2つの「0」に挟まれた「1」をすべて削除する方法を解説します。最終的な文字列には、「0」に囲まれた「1」が一切残らない状態を目指します。

問題の例

入力 : string = "110010"
出力 : "11000"
説明 : インデックス4にある「1」が、前後の2つの「0」に挟まれているため削除されます。

入力 : string = "0010"
出力 : "000"
説明 : インデックス2にある「1」が、2つの「0」に挟まれているため削除されます。

解決のためのアプローチ

ここではシンプルなアプローチを採用します。ループを使って文字列を先頭から順に走査し、各位置について次の条件を確認します。

• 現在の文字が「1」であること
• ひとつ前の文字とひとつ後ろの文字が、どちらも「0」であること

両方の条件を満たす場合、その文字は「0」に挟まれているため削除対象となります。削除を実行すると文字列の長さが変わるため、長さを保持している変数を新しい値で更新します。最後に、処理が完了した文字列を出力すれば完成です。

C++での実装例

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

int main () {
    string str = "110010";
    int length = str.length();

    for (int i = 1; i < length - 1; i++) {
        // 現在の文字が'1'で、前後がどちらも'0'かどうかを確認
        if (str.at(i) == '1' && str.at(i - 1) == '0' && str.at(i + 1) == '0') {

            // 2つの0に挟まれた文字を削除
            str.erase(i, 1);

            // インデックスを1つ戻し、直前の要素を再確認できるようにする
            i--;

            // 削除後に文字列の長さを更新
            length = str.length();
        }
    }

    cout << "2つの0の間の要素を削除した後の文字列: " << str;
    return 0;
}

実行結果

2つの0の間の要素を削除した後の文字列: 11000

コードの解説

• ループを使い、文字列をインデックス1から「length - 2」まで走査します。先頭と末尾には前後の文字が存在しないため、チェック対象外です。
• 現在の文字が「1」であり、かつ前後の文字がどちらも「0」であるかを判定します。この条件により、「0」を誤って削除することを防げます。
• 条件を満たした場合、erase関数でその位置の文字を削除し、インデックスを1つ戻すことで、削除後に新しくできた並びも引き続きチェックできます。
• 削除によって文字列の長さが変化するため、length変数を毎回更新します。
• ループ終了後、更新された文字列を出力します。

計算量について

このアルゴリズムの時間計算量はO(n²)です。erase関数を呼び出すたびに、削除位置以降の文字を前方へシフトする処理が発生するためです。より高速な処理が必要な場合は、条件を満たさない文字だけを別の文字列に順番にコピーしていく方式（O(n)）を採用すると効率的です。

まとめ

この記事では、「0」と「1」で構成される文字列から、2つの「0」に挟まれた「1」を削除する方法について解説しました。紹介したC++プログラムは、同じロジックを使えばC、Java、Pythonなど他の言語でも簡単に実装できます。本記事が皆さまのお役に立てば幸いです。