C++で配列を回転させながら全要素を連結して最大の数を作る方法

本記事では、循環配列（サーキュラー配列）に格納された複数の数値を連結し、可能な限り大きな数を作り出す問題をC++で解きます。循環配列とは、先頭の要素が末尾の要素の直後に続くものとして扱われる配列のことで、キュー（待ち行列）の実装などによく利用されます。

問題の概要

配列内の各要素は、桁数が同じでも異なっていても構いません。目標は、必要に応じて要素を回転（ローテート）させながら数値を連結し、最大の数を生成することです。

この問題は、すべての要素の左端の桁（最上位の桁）に注目することで解けます。その中で最も大きい左端の桁を持つ数が、連結後の数の先頭に配置されるべきです。

• その要素が先頭（インデックス0）にある場合：インデックス1〜n-1の要素をそのままの順序で後に続けます。
• その要素が途中（インデックスi）にある場合：まずインデックスi+1〜n-1の要素を並べ、その後にインデックス0〜i-1の要素を付けます。
• その要素が末尾にある場合：インデックス0〜i-1の要素をその後に付けます。

入力例と出力例

例1

Arr[] = { 121, 43, 65, 32 }

出力：

最大数: 653212143

解説 − 左端の桁が最も大きいのは「6」です。65を先頭に置き、続けて32、121、43と並べます。配列が循環しているため、この順序が成立します。

例2

Arr[] = { 1101, 9, 321, 77 }

出力：

最大数: 9321771101

解説 − 左端の桁が最も大きいのは「9」です。9を先頭に置き、続けて321、77、1101と並べます。ここでも配列が循環配列であることがポイントになります。

アルゴリズムの考え方

以下のプログラムでは、次の手順で最大数を求めています。

• 配列 arr[] に数値を格納します。
• 関数 Largest(int arr[], int n) が配列とその長さ n を受け取り、連結によって作れる最大の数を出力します。
• 変数 maxx は、最も大きい左端の桁を持つ数を保持するためのもので、0で初期化します。
• 変数 pos は、その数のインデックスを記録します。
• i=0からn-1まで各 arr[i] を走査し、数値を10で割り続けて商が0になったときの剰余が左端の桁であることを利用して、各要素の左端の桁を求めます。
• 現在の桁がそれまでの最大値より大きければ、maxx と pos を更新します。
• 最後に、インデックスposから配列の末尾までの要素を出力し、続けてインデックス0からpos-1までの要素を出力します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void Largest(int arr[], int n){
   int maxx = 0;
   int pos = 0; // 最も大きい左端の桁を持つ数のインデックス
   for (int i = 0; i < n; i++) {
      int num = arr[i];
      // 左端の桁を確認
      while (num!=0) {
         int rem = num % 10;
         num = num / 10;
         if (num == 0) {
            if (maxx < rem) {
               maxx = rem;
               pos = i;
            }
         }
      }
   }
   // 最大の数を出力
   cout<<"連結による最大数: ";
   for (int i = pos; i < n; i++)
      cout << arr[i];
   for (int i = 0; i < pos; i++)
      cout << arr[i];
}
int main(){
   int Arr[] = { 12,34,56,98 };
   int size=4;
   Largest(Arr,size);
   return 0;
}

実行結果

連結による最大数: 98123456