[백준] 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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

 

[출력]

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

 

💡 풀이법

1. A~Z까지 각 단어들의 자릿수의 합을 구한다.

( 예를 들어 A를 탐색하는데 어떤 단어 두개가 ABDA, CDAF라면 1001 + 10 = 1011 이 된다 )

2. 자릿수의 합을 리스트에 담는다.

3. 리스트를 오름차순 정렬시킨다.

4. for문을 돌며 리스트에서 하나씩 빼서 num을 곱해 ans에 더한다.

( 이때 num은 9부터 -1씩 줄어든다.)

5. 리스트에서 뺐는데 0이면 for문을 중지한다.

(0이면 더이상 더해줄 알파벳이 없다는 뜻이기 때문)

 

N = int(input())
words = []
for _ in range(N):
    words.append(list(input()))
alphas = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')

lst = []
for a in alphas:
    total = 0
    for word in words:
        for i, b in enumerate(word[::-1]):
            if a == b:
                total += 10**i
    lst.append(total)
lst.sort(reverse=True)

num = 9
ans = 0
for item in lst:
    if item == 0:
        break
    ans += num*int(item)
    num -= 1
print(ans)