[백준1339번] 단어 수학 / Python3

문제

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

단어 수학 문제는 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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

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

예제 입력 1

2
AAA
AAA

예제 출력 1

1998

예제 입력 2

2
GCF
ACDEB

예제 출력 2

99437

예제 입력 3

10
A
B
C
D
E
F
G
H
I
J

예제 출력 3

45

예제 입력 4

2
AB
BA

예제 출력 4

187

나의 풀이

처음에 문제를 접하고 쉬운 문제로 생각했다. 단순히 가장 긴 문자열의 길이부터 시작해 하나씩 9부터 수를 메겨나갔다. 운이 좋게도 위의 예제가 모두 정답이었다. 그러나 제출을 해보면 틀렸다. 자세히 생각을 해보니 같은 자리에 있는 알파벳의 경우에는 우선순위가 필요했던 것이다. 그래서 검색을 통해 해법을 살짝 보았다. 백트래킹으로 모든 경우를 확인해 볼수도 있었지만 나는 수학적으로 접근하는 것이 더 와닿았다.

수학적으로 이 문제를 해결하는 법은 바로 주어진 알파벳의 자리수만큼 값을 곱해주어 가장 큰 값부터 9를 곱해 더해주는 것이었다. 예를 들어보면 다음과 같다.

GCF + ACDEB = 10000*A + 1010*C + 100*G + 100*D + 10*E + F + B

이걸 코드로 풀어내기 위해서는 모든 알파벳을 나타낼 수 있는 배열을 만들고 입력받은 단어에 각 자리수를 곱해가며 특정 알파벳 인덱스의 해당하는 값에 더해주어야 했다. 이후 알파벳 배열에서 0이 아닌 값을 가진것만 뽑아내 내림차순으로 정렬을 한 뒤 큰 값부터 9를 곱해가며 결과값에 더해주었다. 결국 알파벳은 처음 자리값에 대한 정보로만 사용을 하고 마지막 계산을 할때는 필요가 없었다. 이렇게 말하는 것보다 코드를 차근히 읽어보면 이해가 더 쉽게 될 것이다.

코드

# 1339번 단어 수학
import sys, copy

# main
n = int(input())

words = []
alpha = [0 for _ in range(26)]
for _ in range(n):
    words.append(list(sys.stdin.readline().strip()))

for word in words:
    i = 1
    while word:
        alpha[ord(word.pop()) - 65] += i
        i *= 10

nums = []
for a in alpha:
    if not a == 0:
        nums.append(a)

nums.sort(reverse=True)

answer = 0
v = 9
for num in nums:
    answer += (v * num)
    v -= 1

print(answer)