【白俊】1339号-単語数学

18799 ワード
greedy algorithm baekjoon テキストリンク
初めて
アイデア
1)与えられた単語の長さの降順で並べ替える
2)一番長い単語の大きい数字から始め、0から9の間でアルファベットごとに最大値を指定します.
アルファベットと数字のマッチングはdictでいいです.
コード#コード#
N = int(input())
num = list(range(10))
alpha = []
tmp = {}

for _ in range(N):
    alpha.append(input())

alpha.sort(key = lambda x : len(x), reverse=True)

for i in range(N):
    for j in range(len(alpha[i])):
        val = alpha[i][j]
        if len(tmp) == 0:
            tmp[val] = str(max(num))
            num.remove(max(num))
        else:
            if val in tmp:
                continue
            else:
                tmp[val] = str(max(num))
                num.remove(max(num))
result = 0
for i in range(N):
    tmpresult = ""
    for j in range(len(alpha[i])):
        tmpresult += tmp[alpha[i][j]]
    result += int(tmpresult)
print(tmp)
print(result)
2回目
アイデア
最初のアイデアでは少し変形(アルファベット、数字)し、それを組み合わせてソートします.
コード#コード#
N = int(input())
num = list(range(10))
words = []
alpha = []
tmp = {}

for i in range(N):
    word = input()
    words.append(word)
    for j in range(len(word)):
        alpha.append((len(word)-j,word[j]))

alpha.sort(key=lambda x : x[0],reverse=True)

for a in alpha:
    if a[1] in tmp: # 알파벳과 0~9 매칭
        continue
    else:
        tmp[a[1]] = str(max(num))
        num.remove(max(num))

result = 0
for i in range(N):
    tmpresult = ""
    for j in range(len(words[i])):
        tmpresult += tmp[words[i][j]]
    result += int(tmpresult)

print(result)
反例
2
AB
BB
正解
出力結果=186
終局
アイデア
いっそ座席価格に応じた価格を計算したらどうですか?という考えが生まれた.上記の反例を例にとると、A=10 B=12であるため、Bはより大きな値を割り当てる必要がある.それなら反例の場合も解決できる.
1)単語入力を受け付ける.
2)アルファベット値を計算し、対応するアルファベットに値を割り当てます.
3)降順に並べます.
4)値の大きいアルファベットから,0−9の残りの値のうち,値の大きいものから割り振る.
5)単語を数字に変換する.
コード#コード#
N = int(input())
num = list(range(10))
words = []
tmp = {}
new = {}

for _ in range(N):
    words.append(input())

for word in words:
    for i in range(len(word)):
        if word[i] in tmp:
            tmp[word[i]] += (10**(len(word)-i-1))
        else:
            tmp[word[i]] = (10**(len(word)-i-1))

tmp = sorted(tmp.items(), key = lambda x : x[1], reverse= True)

num = 9
for i in range(len(tmp)):
    new[tmp[i][0]] = num
    num -= 1

result = 0
for word in words:
    tmpresult = ""
    for w in word:
        tmpresult += str(new[w])
    result += int(tmpresult)
print(result)
gradleパッケージ指定パッケージとクラスのjar
AndroidでViewPagerを解決ページ数が3未満の場合、ページスライドブランクバグ