[백준 1339] 단어 수학

[BanApp]

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

python3

import sys
from string import ascii_uppercase

n = int(sys.stdin.readline())

ans = 0
arr = []
dic = {}
v_dic = {}

#할당 받을 수 있는 값들의 리스트
num = [0,1,2,3,4,5,6,7,8,9]

for _ in range(n):
    arr.append(sys.stdin.readline().rstrip())

# A ~ Z 딕셔너리 생성
for i in ascii_uppercase:
    dic[i] = -1 # 실제 할당값
    v_dic[i] = 0 #자릿수합

#v_dic에 자릿수의 합 넣어주기
for i in arr: 
    i = list(i)
    for j in range(len(i)):
        v_dic[i[j]] = v_dic[i[j]] + 10**(len(i)-(j))

#오름차순으로 v_dic 정렬
v_dic = sorted(v_dic.items(), key = lambda x:x[1]) 

#dic에 할당값 넣어주기
while num: 
    x,y = v_dic.pop()
    dic[x] = num.pop()


#입력받은 문자열을 할당값에 맞게 치환
for i in arr:
    i = list(i)
    for j in range(len(i)):
        i[j] = str(dic[i[j]])
    x = "".join(i)
    ans = ans + int(x)

#정답출력
print(ans)

자릿수의 합이 클수록 큰 수를 가져야 유리하다. 따라서 그리디 알고리즘.
98765가 9x10^5 + 8x10^4 + 7x10^3 ... 이런식으로 표현되는걸 생각해보면 된다.
v_dic 딕셔너리에 해당 알파벳의 자릿수의 합의 값을 넣어주고 dic에는 해당 알파벳에 할당되는 실제 값을 반복문을 통해서 넣어주면 된다.
마지막에 입력받은 문자열을 정수로 치환해서 모두 더해주면 끝! so ez