Pythonで最大の数を作る方法：cmp_to_keyを使ったカスタムソートの実装

負でない整数のリストが与えられたとき、それらをうまく並べ替えて、可能な限り大きな数を作ることを考えます。例えば、配列が [10, 2] の場合、最大の数は「210」となります。

解き方のアプローチ

この問題を解くには、以下の手順に従います。

• まず、すべての整数を文字列に変換します。
• 2つの数値 x と y を比較する際は、単純な大小比較ではなく、「x を先に置いた場合（x+y）」と「y を先に置いた場合（y+x）」の連結結果を比べます。より大きい数になる順序でソートすることで、最も桁の並びが有利な配置になります。
• ソートが完了したら、すべての数値を連結して結果の文字列を返します。

実装例

以下は、Pythonの functools.cmp_to_key を利用してカスタム比較関数でソートを行う実装例です。lstrip("0") or "0" の部分は、[0, 0] のようにすべてがゼロの場合に「00」ではなく「0」を返すための工夫です。

from functools import cmp_to_key
class Solution(object):
    def largestNumber(self, nums):
        for i in range(len(nums)):
            nums[i] = str(nums[i])
        nums.sort(key=cmp_to_key(lambda x,y:self.compare(x,y)))
        return "".join(nums).lstrip("0") or "0"
    def compare(self,x,y):
        if x+y<y+x:
            return 1
        elif x+y == y+x:
            return 0
        else:
            return -1
ob1 = Solution()
print(ob1.largestNumber([3,30,5,6,8]))

入力

[3,30,5,6,8]

出力

"865330"

ポイントの解説

このアルゴリズムの鍵となるのは、compare 関数です。例えば「3」と「30」を比較する場合、「330」と「303」を比べると「330」の方が大きいため、3が30より先に来るべきだと判断できます。このように連結結果そのものを比較基準にすることで、どのような組み合わせでも正しく最大の数が得られます。計算量はソートに依存し、O(n log n) となります。