[백준/Python] BOJ 1339 - 단어 수학

👀 문제

1339번: 단어 수학 ✨ 골드 4

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

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

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

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

🔑 키포인트

자릿수

✍️ 코드

import sys
input = sys.stdin.readline

n = int(input())
str_dict = {} # key: 알파벳, value: 자릿수 총합 담을 딕셔너리 생성
result = 0 # 정답

str_arr = [list(input().rstrip()) for _ in range(n)]

# 단어 자릿수로 10제곱 해 주기
# 세 글자면 첫 번째 자리는 10^2, 두 번째 10^1, 세 번째 10^0
for word in str_arr:
    for i in range(len(word)):
        if word[i] not in str_dict:
            str_dict[word[i]] = 10 ** (len(word) - i - 1)
        else:
            str_dict[word[i]] += 10 ** (len(word) - i - 1)

# 내림차순 해 주기
sorted_arr = sorted(str_dict.items(), key=lambda x: x[1], reverse=True)

# 앞에서부터 값에 9 곱해 주기
start = 9
for i in range(len(sorted_arr)):
    sorted_arr[i] = (sorted_arr[i][0], sorted_arr[i][1] * start)
    start -= 1
    result += sorted_arr[i][1]

print(result)