C++で数値内の連続する重複桁を削除する方法

この記事では、数値 n が与えられたとき、その中に含まれる連続する重複桁を削除する方法を解説します。

入力: x = 12224
出力: 124

入力: x = 124422
出力: 1242

入力: x = 11332
出力: 132

ご覧のとおり、隣り合って繰り返されている桁だけが削除され、離れた位置にある同じ数字はそのまま残ります。この問題では、数値のすべての桁を走査しながら、重複している桁を取り除いていきます。

解決のためのアプローチ

このアプローチでは、n の各桁を右から左へ順番に調べていきます。具体的には、n を 10 で割った余り（n % 10）で最下位の桁を取り出し、その後 n を 10 で割ることで次の桁へ進みます。

取り出した現在の桁を直前の桁と比較し、以下のように処理を分けます。

• 両者が等しい場合（重複している場合）： その桁は新しい数値に加えず、そのまま次の桁へ進みます。
• 両者が異なる場合： その桁を新しい数値に追加し、直前の桁の情報を現在の桁で更新してループを継続します。

この処理を n が 0 になるまで繰り返すことで、重複桁が削除された新しい数値が完成します。処理量は桁数に比例するため、計算量は O(d)（d は桁数）となります。

C++での実装例

#include <bits/stdc++.h>

#define MOD 1000000007

using namespace std;

int main() {
   int n = 1222333232; // 対象となる数値
   int new_n = 0; // 重複を削除した新しい数値
   int po = 1; // 新しい数値の桁位置を管理する10の倍数
   int prev = -1; // 直前の桁
   int curr; // 現在の桁
   while(n) {
      curr = n % 10;
      if(prev != curr) { // 直前の桁と重複していない場合のみ処理
         new_n = new_n + (curr * po); // 新しい桁を new_n に追加
         po *= 10;
         prev = curr;
      }
      n /= 10;
   }
   cout << new_n << "\n";
   return 0;
}

出力

123232

コードの解説

上記のコードでは、n の各桁を順番に走査しています。直前の桁（prev）と現在の桁（curr）が一致しない場合にのみ、その桁を新しい数値 new_n に追加します。桁を追加する際は、変数 po（10 の累乗）を使って正しい桁位置に配置し、追加後に po を 10 倍して次の桁位置へ備えます。一方、現在の桁と直前の桁が一致する場合はこのブロックをスキップし、n が 0 になるまでループを継続します。

なお、桁を右から左へ処理するため、元の数値の桁の並び順は自然に保たれます。また、大きな数値を扱う場合は int 型の範囲を超える可能性があるため、long long 型を使用するとより安全です。

まとめ

この記事では、数値から連続する重複桁を削除する問題を解決しました。C++による実装例と、右から左へ桁を走査して直前の桁と比較するというシンプルで効率的なアプローチを学びました。同じロジックは、C、Java、Python など他の言語でも同様に実装できます。この記事が皆さんの学習のお役に立てば幸いです。