[python] 백준 > 그리디 > 단어 수학(1339)

[문제]

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

 

www.acmicpc.net/problem/1339

1339번: 단어 수학

[풀이]

import sys
input = sys.stdin.readline

N = int(input())
words = [list(input().rstrip()) for _ in range(N)]

word_dict = {}

for word in words:
    k = len(word)-1
    for w in word:
        if w in word_dict:
            word_dict[w] += 10 ** k
        else:
            word_dict[w] = 10 ** k
        k -= 1

sorted_word = sorted(word_dict.values(), reverse=True)
answer, num = 0, 9
for sw in sorted_word:
    answer += sw * num
    num -= 1
print(answer)

• 단어의 스펠을 하나씩 꺼내 1의자리 숫자인지 10의 자리 숫자인지 10의 n승의 자리 숫자인지 확인한 후 같은 스펠링을 가지고 있으면 더해준다.
• 그리디 방식을 통해 가장 큰 값부터 9부터 곱해준다

[다른 사람의 풀이]

import sys
input = sys.stdin.readline
t = int(input())
words = [input().strip() for _ in range(t)]
importance = {}
for word in words:
    for idx, w in enumerate(word[::-1]):
        if not importance.get(w,0):
            importance[w] = 10**idx
        else:
            importance[w] += 10**idx
tmp = sorted(list(importance.items()), key=lambda x: x[1],reverse=True)
alpha_to_idx = {a:9-idx for idx, (a,b) in enumerate(tmp)}
score = 0
for word in words:
    for idx, w in enumerate(word[::-1]):
        score += alpha_to_idx[w]*10**(idx)
print(score)