220509 - 단어 수학

◾단어 수학 : 백준 1339번

• 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개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

---

입력

• 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다.
• 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다.
  • 단어는 알파벳 대문자로만 이루어져있다.
  • 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다.
  • 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

• 첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

입출력 예

Input	Output
2 AAA AAA	1998
2 GCF ACDEB	99437
10 A B C D E F G H I J	45
2 AB BA	187

---

◾ 풀이

1. 해설

• 가장 값을 크게 만들기 위해서는 높은 자리수에 많이 위치한 문자에 높은 값을 부여하는 것이다.
• 따라서, 문자의 자리수 합이 클 수록 높은 값을 가지면 된다.
  • 각 단어의 각 문자의 자리수를 구하고 같은 문자끼리 합한다.
  • 자리수의 합이 높은 문자부터 차례로 9, 8, 7, ... 순으로 숫자를 부여한다.
    • [자리수의 합 * 해당 문자의 숫자]

---

2. 프로그램

1. 단어의 개수 n 입력
2. 단어 입력
   • 단어에 포함된 문자의 자리수 계산
   • dict형을 사용해 결과 누적
3. dict형의 value로 내림차순 정렬하여 문자 -> 숫자 변환
   • value * (9, 8, 7, ...) 순으로 계산하여 합한다.
4. result 출력

# 코드
n = int(input())

charToNum = {} # 문자의 자리수 합을 저장할 dict

for _ in range(n):
    word = input()  # 단어 입력
    # 단어에 포함된 문자의 자리수 계산
    # 단어의 뒤부터 차례로 1의 자리, 2의 자리, ...
    for i, ch in enumerate(word[::-1]):
        if ch not in charToNum:
            charToNum[ch] = 0
        charToNum[ch] += 10 ** i

result = 0  # 결과 저장
# 자리수의 합(dict의 value)로 내림차순 정렬하여 결과 계산
# 높은 값부터 차례로 9, 8, 7, ...로 지정
for i, (key, value) in enumerate(sorted(charToNum.items(), key=lambda x : -x[1])):
    result += value * (9-i)

print(result)