説明:

これはプログラマーの大数題です.
与えられた整数を組み合わせて、生成可能な最大数の問題を返し、例えば[6,10,2]は、多くの組み合わせがあってもよいが、6210は最大数の組み合わせである.入力値1～1000の間には、最大10,000個の数値を入力できます.したがって、組み合わせの結果は整数ではなく文字列を返さなければなりません.

に答える

不可能な再帰的なナビゲーション、単純なソート

10万個の数字がある可能性があるため、再帰検索で文字列を組み合わせたり比較したりすることはできません.したがって,最初に考えられる方法は,与えられた数字を並べ替え,大きな順序で組み合わせることである.
しかし問題では1個から4個の数字を与えることができるので、[3300]があれば300と3の順に3003に組み合わせる.しかし最大の組み合わせは3と300の順に組み合わせられた3300である.したがって,単純なソートでは解決できない.

文字列の入力

その結果,ネット上で解説語を検索して解くことができ,特殊に与えられた数字を文字列に変換し,4個程度を接続して並べ替える方法である.

def solution(numbers):
    # 주어진 숫자를 문자열로 바꿔서 4번 반복해서 조합한 후 튜플로 리스트에 저장.
    comparing_numbers = [(str(number), str(number) * 4) for number in numbers]
    # 조합된 문자열을 기준으로 내림차순 정렬.
    compared_numbers = sorted(comparing_numbers, key=lambda x: x[1], reverse=True)
    # 정렬된 문자열을 조합한 후 정수로 변환한 후 다시 문자열로 변환.
    return str(int("".join([compared_number[0] for compared_number in compared_numbers])))

なぜそうなったのか分かりませんが、問題でどのようなソートが求められているのか、Pythonで文字列をどのようにソートしているのかを見つけて理解しました.
まず、問題の例を見ると、与えられた数字が次のように並べられていることがわかります.

[6, 10, 2] => [6, 2, 10] => "6210"

[3, 30, 34, 5, 9] => [9, 5, 34, 3, 30] => "9534330"

与えられた数字を並べ替える場合は、一般的な整数や文字列の比較ではなく、単語ごとに比較し、最初の文字に準じて先に並べ替えます.同じ数字があれば、次の文字を使用して比較します.34、30を例にとると、2つの整数は「34」、「30」に変換され、最初のアルファベットは「3」に等しい.したがって、2番目の文字「4」は「0」よりも4が大きいので、「34」は「30」よりも優先度が高いと考えられる.
でも3、30はどうですか?「3」、「30」の最初の字も「3」です.だから2文字目で比較すると、「3」は2文字目がないので比較できません.では、「3」が「30」より優先度が高いとどう判断するのでしょうか.
解説で提供されているアイデアは、すべての数字を繰り返し貼り合わせて、次のようにパッチを打つことです.

3 -> "3"* 4 -> "3333"

30 -> "30"* 4 -> "30303030"

問題では,1から最大1000までの整数を明確に指摘した.したがって、1桁でも4回繰り返して文字列として埋め込み、4桁の整数と比較します.
4桁になるためなら「0」を3回加えて4桁にすることもできますが、「3000」と「30000」の方が「30000」の方が大きいです.したがって、「0」ではなく、「3333」や「30303030」と元の数字を繰り返し比較すると、「3333」の方が大きく、3を30の前に並べることができると考えられます.

Pythonの文字列、整数ソート

結論を先に言っただけなのに、なぜこう比較するのか.これはPythonにおける整数と文字列の並べ替えの違いから分かる.

>>> sorted(['3333', '30303030'])
['30303030', '3333']
>>> sorted([3333, 30303030])
[3333, 30303030]

文字列「3333」と「3030303030」を比較すると「3333」の方が大きく、整数3333と30303030を比較すると「3030303030」の方が大きくなるのは当然です.なぜ文字列の結果が逆なのでしょうか.
はPythonで文字列を比較すると上のように逐字比較されるからです.上の「3333」と「30303030」を比べると、最初の字は「3」です.しかし次の字では「3333」の「3」が「30303030」の「0」よりも大きいため、ここでの比較は中断され、「3333」の方が大きい.
文字列がどんなに長くても、一字ずつ比較するときにもっと大きな側が現れたら、比較は終わります.逆に「123」と「12345」を比較すると、どちらも「12345」の方が大きいということがわかります.

>>> sorted(["123", "12345"])
['123', '12345']
>>> sorted([123, 12345])
[123, 12345]

このとき「123」と「12345」を3文字目と比較しても同じなので、文字が多いと判断した「12345」の方が大きい.わかりやすく比較すると以下のようになります.

>>> ["1","2","3", "", ""] < ["1","2","3","4","5"]
True
>>> "" < "4"
True
>>> "" < "5"
True

質問に必要なソート

この問題はプログラマによってソート問題に分類される.では、問題を必要な最大値に組み合わせる方法をどのように見つけますか?指定された整数は1～1000の間であるため、比較対象は1つの位置文字から4つの位置文字列まで等しくありません.
前述したように、「34」および「30」の優先順位は「34」より高く、「3」および「30」の優先順位は「3」より高くなければならない.「30」の2文字目の「0」は「3」より小さいため、「303」に組み合わせることはできません.
もちろん、「3」と「34」の優先順位は「34」であるべきである.この場合は「334」ではなく「343」に組み合わせるからです.ここで注目すべき点は、重複する異なる長さの数字文字列を比較する場合、比較対象(「34」)の次の文字(「4」)が自分(「3」)の前の文字(「3」)よりも大きい場合、優先度が高くなることである.
同様に、「3」と「30」も比較対象(「30」)の次の文字(「0」)が自分(「3」)の前の文字(「3」)よりも小さいと考えられるので、「3」は「30」よりも優先度が高い.次の字は自分より大きいので、前の組み合わせの時にもっと大きな結果を得ることができます.
さらに長い例では、「1231」と「123」がある場合、比較対象(「1231」)の次の文字(「1」)は、自分(「123」)の前の文字(「3」)よりも小さいので、自分の優先度が高いはずです.だから「1231231」ではなく「1231123」であるべきだ.
そして,この次の字,前の字の比較手法を用いて,数字文字列を4回繰り返し接続する方法と文字列比較ロジックを用いた.

ポスト

実は、私はパズルを見て、たくさん理解しましたが、もし本当にこのような問題が発生したら、私一人では解決できないと思います.これはおかしいが不思議な問題だ.

リファレンス

元のファイル