[백준] 1339번 단어 수학 (파이썬)

난이도 : GOLD IV

문제링크 : https://www.acmicpc.net/problem/1339

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.
단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.
예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

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

문제 해결 아이디어

• 단어의 길이가 숫자 자릿수라고 생각했을때 가장 긴 단어의 맨앞 부터 9,8.. 대입해야 가장 큰숫자를 만들수 있다.
• 딕셔너리를 통해 각 단어마다 자릿수에 비례한 숫자를 대입한다
  • ex) ABC => dic = { A: 100, B: 10, C: 1}
• 완성된 딕셔너리의 value 값들을 큰순으로 정렬한다음 9,8,7.. 곱해준다.

소스코드

import sys
from collections import defaultdict

input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
  arr.append(input().strip())
dict = defaultdict(int)
for i in arr:
  for j in range(len(i)):
    dict[i[j]] += 1 * (10 ** (len(i)-1-j))

m = 9
answer = 0
for i in sorted(dict.values(), reverse=True):
  answer += i * m
  m -= 1

print(answer)