단어수학

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

1339번: 단어 수학

문제요약:

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

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

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

 

난이도:

골드4

 

소요시간:

18분

 

제출횟수:

1회

 

코딩:

import sys
from collections import defaultdict
input = sys.stdin.readline

n = int(input())
arr= [input().strip() for _ in range(n)]
num = [i for i in range(9,-1,-1)]
#num은 사용될 숫자리스트

Count = defaultdict(int)
for alphas in arr:
    for i,alpha in enumerate(list(alphas)[::-1]):
        Count[alpha] += 10**i
ans = 0
for a,b in zip(num,sorted(list(Count.values()),reverse = True)):
    ans +=a*b

print(ans)

주어진 알파벳들에 숫자를 하나씩 할당하여 주어진 문자열 즉 숫자들의 합이 최대가 되도록 만드는 문제입니다.

예시를 들면 문제의 예시처럼 GCF + ACDEB 가 주어질때 이 합을 문자가 포함된 수식으로 바꾸면,

G*100+C*10+F    +   A*10000+C*1000+D*100+E*10 +B 다음과 같이 나타낼 수 있습니다. 이때 C는 중복되므로

C만 1010이 계수가 되게 됩니다. 즉 각 문자열의 순서의 맞게 계수를 설정해준뒤 이를 더해주고 이를 내림차순으로 정렬한다음 앞에서 부터 할당 할 수 있는 가장 큰수인 9,8,7 ... 순으로 할당해주는 것이 문제의 해결법이라고 할 수 있습니다.

 

Count를 설정하고 그 밑에 세줄을 통해 계수를 더해준후 Count를 출력해보면

defaultdict(<class 'int'>, {'F': 1, 'C': 1010, 'G': 100, 'B': 1, 'E': 10, 'D': 100, 'A': 10000})

다음과 같이 나오게 되고, 이에 value값들만 뽑은후 내림차순으로 정렬하게 되면, 이는

sorted(list(Count.values()),reverse = True)
# > [10000, 1010, 100, 100, 10, 1, 1]

다음과 같고 아래를 나타냅니다. 이를 zip함수로 위에 설정해준 [9,8,7, ... ,3,2,1,0] 함수와 묶어준뒤

(이때 무조건 num의 길이가 위의 리스트보다 같거나 길텐데 zip은 짧은 함수 기준으로 묶어줍니다. 만약 긴것을 기준으로 묶으려면 긴거기준으로 짧은거 뒤에 할당해주거나 itertools 에 zip_longest()함수 사용 ex) zip_longest(a,b,fillvalue=0)     ) 

서로 곱하면 결국 가장 많이 필요한(계수가 가장 큰) 알파벳부터 큰숫자가 (9부터) 할당되어 합이 가장 크게 도출 됩니다.(만약 계수가 같다면 둘중에 뭘 할당 해주어도 합값은 같으므로 상관 없음)

 

약간의 수학적인 개념이 들어가서 어렵지 않게 풀 수 있었던 것 같습니다.