백준 1339 파이썬 - 단어 수학

https://www.acmicpc.net/problem/1339

1339번: 단어 수학

문제

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

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

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

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

코드

import sys
n = int(sys.stdin.readline())
arr = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
alpha = [0 for _ in range(26)]
for i in range(n):
    a = 0
    for word in arr[i][::-1]:
        alpha[ord(word) - ord('A')] += (10 ** a)
        a += 1
alpha.sort(reverse=True)
result = 0
num = 9
for i in alpha:
    if i == 0:
        break
    result += (num * i)
    num -= 1
print(result)

풀이

A가 1의 자리에 한번 나오면 1을 alpha에 알파벳 순서에 맞게 저장하고, 만약 100의 자리에 두번, 10의 자리에 한번 나오면 110을 저장하는 방식으로 저장한다. 그 후 내림차순으로 sort해주면 가장 큰 값이 처음으로 오고 그 값부터 9를 지정하고 다음 값은 1을 줄인 8을 지정하는 형식으로 만든다. 숫자를 다 더해 출력하면 된다.