[백준] 1339번: 단어 수학

문제

백준 - 1339번: 단어 수학

분석

주어진 단어들을 치환하여 더했을 때 가장 큰 값을 구하는 문제이다. 각 단어들의 알파벳은 0 ~ 9중 하나로 바꿀 수 있고, 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

code.plus에서 순열 카테고리에 있어서 완전 탐색으로 하려다가 시간초과로 실패했다.
이 문제는 그리디로 분류되었다.
그리디하게 생각해보면 자릿수가 가장 높은 것에 9부터 할당하면 된다.
그러나 같은 자릿수일 때 동등한 우선순위가 아닐 수 있다.
ex) AB, BB가 있을 때 B가 9 A가 8을 할당받아야 가장 큼

따라서 할당받기 전에 각 알파벳이 가지는 기본 값을 먼저 구하고, 그것을 내림차순하여 순서대로 9부터 부여받으면 된다.

기본 값은 자릿 수에 따라 10의 자릿수-1제곱을 해주어 더해준다.
이때 여러 번 나오는 알파벳은 추가로 더해지기 때문에 우선순위가 더 높아진다. (이 값까지 같으면 우선순위가 같음)

기본 값들을 내림차순하고 순서대로 9부터 부여하면서(곱하기) 누적하면 답을 구할 수 있다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n = int(input())
words = []
for _ in range(n):
    words.append(input().rstrip())

dic = {}
for word in words:
    x = len(word)-1
    for a in word:
        if a in dic:
            dic[a] += 10**x
        else:
            dic[a] = 10**x
        x -= 1
values = sorted(dic.values(), reverse=True)
ans = 0
num = 9
for val in values:
    ans += val*num
    num -= 1
print(ans)

끝으로..

그리디였다는 것을 알았다해도 어려웠을 것 같다.
부족한 실력을 채울 방법에 지름길이 없다. 꾸준히 문제를 더 풀어야겠다.