백준 1339 단어수학

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

1339번: 단어 수학

📌 해결순서

알파벳을 숫자로 바꾸는 현재시점에서 할수 있는 최선은?

예제의 ACDEB를 숫자로 바꾸면 98753 이 되는데 A를 9로 바꾼 이유는?

숫자의 최댓값을 구하기 위해서 자릿수가 가장 큰 자리에 가장 큰 수를 주면 된다.

A의 자릿수는 만의자리 , 10000 이기 때문에 가장 큰 수인 9로 바꾼다

 

1. 숫자의 자릿수를 저장하는 딕셔너리를 만든다

2. 알파벳이 key,  그 알파벳을 숫자로 바꿨을때의 자릿수가 value

3. 만약 각 단어에 중복되는 알파벳이 있다면 자릿수를 더해준다

ACDEB , GCF 에서 C가 천의자리, 십의자리에 모두 있기때문에 1000 + 10 = 1010 으로 만들어준다

4. 숫자의 자릿수는 같은데 알파벳이 다르다면 어떤 숫자를 주든지 값은 동일하게 나온다

ACDEB , GCF 에서 D, G의 자릿수가 100으로 같은데 

i) D = 7 , C = 6 인 경우, 

ii) C = 6 , D = 7 인 경우 , 99437로 동일한 결과가 나온다.

 

📌 코드

import sys
input = sys.stdin.readline

n = int(input())
lst = []
digit = dict()
ans = 0

for _ in range(n):
    word = input()
    lst.append(word[: -1])

for word in lst:
    tmp = len(word) - 1
    for c in word:
        if c not in digit:
            digit[c] = 10 ** tmp
        else:
            digit[c] += 10 ** tmp
        tmp -= 1

sorted_digit = sorted(digit.values())
multi_num = 9 - len(digit) + 1

for num in sorted_digit:
    ans += num * multi_num
    multi_num += 1

print(ans)