【Python 3】私が忘れたことを恐れている金俊|単語数学(創意)

白俊1339号単語数学!!
次のように、<質問>、<入力>、<出力>を投稿に移動します.

質問する

民植は数学塾で単語の数学問題を知る宿題を受けた.
単語数学の問題はN個の単語からなり、各単語はアルファベットの大文字だけからなる.このとき,問題は,各アルファベットの大文字を0から9の数字のうちの1つからNの数字に置き換えることである.同じアルファベットを同じ数字に変えるには、2つ以上のアルファベットを同じ数字に変えることはできません.
例えば、GCF+ACDEBを算出する場合、A=9、B=4、C=8、D=6、E=5、F=3、G=7と判定された場合、2つの数の和は99437となり、最大値となる.
N個の単語がある場合は、プログラムを作成して最大にします.

入力

1行目は単語の個数N(1≦N≦10)を与える.2行目からN行目で単語1行1個.単語はアルファベットの大文字だけで構成されています.各単語に含まれるアルファベットは最大10文字で、数字の最大長は8です.異なる文字は異なる数字を表す.

しゅつりょく

指定した単語の和の最上位値を1行目に出力します.

どうやって近づくの?

白俊の質問を見るといつも感じられる…!
頭の中では分かりますが、コードを書くには迷います
実際,貪欲法問題は与えられた場合の最適解を解くアルゴリズムである.
他のアルゴリズムに比べて問題は簡単です(もちろん私もよくできません)

初めて近づく...!

最初は、もっと大きな数字のアルファベットに大きな数字を与える方法を考えました.
しかし、間もなく以下の問題が発見された.

に質問

ABC 1個とBB 9個が入力されている場合を考えてみましょう!
A=9、B=8、C=7の場合、987+88*9=1779
A=8、B=9、C=7の場合、897+99*9=1788
長い単語の前列のアルファベットが大きい.
必ずしも最高値を出す必要はありません!
もっと長い単語の前列文字に焦点を当てるよりも
私たちが要求した結果値に焦点を当て直しました.

2度目の接近...!

ABCとEFが与えられたと仮定する
ABC+EFは式で次のように表される
(結果値)=100 A+10(B+C)+1(C+F)
もう一つの状況を表現しましょう.
ABB+ABの場合は次のようになります
(結果値)=100 A+10(B+A)+1(2 B)
この結果値をそれぞれA、Bと組み合わせると、以下のようになります.
(結果値)=110 A+12 B
ここから来た考え.
Aという名前の鍵を作成し、110の値を
Bという名前の鍵を作成し、12という名前の値を割り当てます.
value値を降順に並べる
9.. 8.. 7.. 6.. . . . こんなに大きな数を与えて!

完了したコード

n = int(input())
answer = 0
saving = {}
values = []
num = 9

for _ in range(n):
    word = input()
    for s in range(len(word)):
        if word[s] in saving:
            saving[word[s]] += 10 ** (len(word) - 1 - s)
        else:
            saving[word[s]] = 10 ** (len(word) - 1 - s)

# print(saving)

for i in saving.values():
    values.append(i)

values.sort(reverse = True)

#print(values)

for j in values:
    answer += num * j
    num -= 1

print(answer)

答えは求めた最終的な答えだ.
savingは、A:111やB:12など、各アルファベットの重みを保存するバイナリファイルです.
valuesはsaveのvalues値を管理するための空のリストです!

for _ in range(n):
    word = input()
    for s in range(len(word)):
        if word[s] in saving:
            saving[word[s]] += 10 ** (len(word) - 1 - s)
        else:
            saving[word[s]] = 10 ** (len(word) - 1 - s)
         

上記のコードでアルファベットを初めて入力すると、
キーとValueを対応する値に初期化します.
コードが記述され、dickshernerにアルファベットが存在する場合は、所定の値に加算されます.

for i in saving.values():
    values.append(i)

values.sort(reverse = True)

saveに保存した値を空のリスト値に保存します.
.sort(reverse=True)で降順に並べ替えます.

for j in values:
    answer += num * j
    num -= 1

valuesは、重みの最大の順序と降順でソートされます.
9から順に1を減らし、乗算した値を答えに加算します.