백준, 단어 수학, 1339

[유형]

그리디

 

[문제링크]

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

 

[요약]

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

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

 

[문제풀이]

예를 들어, GCF + ACDEB를 계산한다고 할 때,

words[G] = 10^2, words[C] = 10^1 + 10^3, ... , words[B] = 10^0을 저장한다.

{'G': 100, 'C': 1010, 'F': 1, 'A': 10000, 'D': 100, 'E': 10, 'B': 1}

딕셔너리 words의 values()를 내림차순으로 정렬한다.

[10000, 1010, 100, 100, 10, 1, 1]

words_sort의 값에 9부터 차례로 곱한 뒤 더한다.

 

import sys
import heapq
def input():
    return sys.stdin.readline().rstrip()

N = int(input())
alphabet = [input() for _ in range(N)]
words = {}

for alpha in alphabet:
    x = len(alpha) -1
    for a in alpha:
        if a in words:
            words[a] += 10**x
        else:
            words[a] = 10**x
        x -=1

words_sort = sorted(words.values(), reverse=True)

result = 0
num =9
for ws in words_sort:
    result += ws * num
    num -= 1
print(result)