[백준 1339번] 파이썬 - 단어 수학

백준 1339 - 단어 수학

시간 제한 2초, 메모리 제한 256MB

# 조건

• 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.
• 단어 수학 문제는 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이다.
• 서로 다른 문자는 서로 다르 숫자를 나타낸다.

# 접근 방법

• 등장하는 모든 알파벳에 9부터의 점수를 순열로 대입하여 구한다면 시간 초과가 발생한다.
• 따라서, 조금은 그리디적인 아이디어가 필요하였다.
• 각 알파벳이 몇 번 등장하는지가 아닌, 얼마나 큰 숫자를 만들 수 있냐가 중요하다.
• 즉, 어느 자리에 해당 알파벳이 등장하는지를 체크해주어야 한다.
• DICTIONARY에 등장하는 알파벳의 자리 값을 더해준다.
• ACDEB의 경우 'A' : 10000, 'C' : 1000과 같이 등장할 때 마다 값을 더해준다.
• 이후, VALUE 값을 내림차순 정렬한다면 각 알파벳들로 만들 수 있는 최고의 자리수 값이 나오게 된다.
• 제일 앞에 있는 자리수 값부터 9~1까지 곱해주며 더하면 최대 합이 나온다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from collections import defaultdict


N = int(input())
words = []
cnt = defaultdict(int)
maxLeng = 0
for _ in range(N):
    t = input().strip()
    words.append(t)
    state = len(t) -1
    for w in t:
        cnt[w] += 10 ** state
        state -= 1
val = sorted(cnt.values(), reverse=True)
result = 0
num = 9
for i in val:
    result += i * num
    num -= 1
print(result)