数字断片をつなげて最大の数を作る

小さなナンバープレート店を思い浮かべてください。箱には数字が刻まれた金属の断片があります: [3, 30, 34, 5, 9]。お客さんが「この断片を全部1列につなげて、作れる最大の番号を作ってください!」と言います。

断片をどんな順番でつなげれば最大の数になるでしょうか?

罠 — 「数値の大きさ順」は間違い

最初に思いつくのは「大きい数字から並べよう」です。数値の降順で並べると 34, 30, 9, 5, 3 → 3430953。

もっともらしく見えますが、間違った答えです。正解は 9534330 です。

なぜでしょう? 9 は 34 より小さい数字ですが、先頭に 9 を置くと先頭の桁が9になり、全体の数がずっと大きくなります。つまり「断片の数値」ではなく「つなげたときにどちらが大きいか」が本当の基準なのです。

特に紛らわしいのが 3 と 30 です。どちらを前に置くべきでしょう?

330 > 303 なので、3が前に来るべきです。数値では30が大きいのに、つなげてみると3が先に来た方が大きい数になるのです。

ここでソートの発想が出てきます。2つの断片 a, b の順序を決めるとき、数値ではなくつなげた文字列を比較します。

この1行の比較ルールをソートの基準(comparator)として差し込むだけです。

なぜ文字列比較で正しい? a+b と b+a は常に同じ長さです(2つの断片を合わせた長さ)。長さが同じ2つの数の大小は先頭の桁から比べればよく、それがまさに文字列の辞書順比較と一致するからです。

いくつか実際に当ててみるとルールが手に馴染みます。

こう比較して降順に並べると断片の順は 9, 5, 34, 3, 30 になり、全部つなげると 9534330 — 正解です。

最後にもう一つだけ罠を。断片がすべて0なら([0, 0])、つなげた結果が "00" になりますが、答えは "0" 1つであるべきです。ソート後の先頭文字が '0' なら "0" だけを返せばきれいに解決します。

まとめると、こういう流れです。

1. すべての断片を文字列に変換する

2. a+b vs b+a の比較で降順ソートする

3. 並べた断片を順につなげる

4. 先頭が '0' なら "0" だけを返す

断片が a+b vs b+a の比較(黄)を経て位置を入れ替え(赤)、1マスずつ最終的な順序に確定(緑)していく全工程をステップ別の可視化で用意しました。各比較で "330" vs "303" のような文字列がどう勝負を決めるか一目で分かります。

「なぜ30より3が先に来るの?」は文章だけだと紛らわしいですが、2つの文字列が並べて比較されるのを一度見れば、「つなげて大きい方が勝つのか」が一瞬で分かります。