[Python] 백준 1339번 : 단어 수학

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

1339번: 단어 수학

---

 문제 풀이

그리디 알고리즘 문제이다.

 

등장한 알파벳 자릿수에 맞춰서 수의 크기를 부여해주면 된다.

예를 들어서, ABCAE에서 A는 10010을, B는 1000을 부여받는 것이다.

내림차순으로 정렬해주고 9부터 차근차근 크기를 부여해주면 된다.

 느낀 점

처음에는 순열로 등장하는 모든 수에 대해서 경우의 수를 따졌는데 당연히 시간 초과가 났다..

정말 고민하다가 약간의 힌트를 받아서 푼 문제이다. 이런 아이디어는 경험으로 익숙해지는 것 같다.

 코드

import sys

N = int(sys.stdin.readline())
numbers = []
dict = {}

for _ in range(N):
    tmp = sys.stdin.readline().strip()
    numbers.append(tmp)
    for idx, x in enumerate(tmp):
        dict[x] = dict.get(x, 0) + 10 ** (len(tmp) - idx - 1)
        
dict_values = list(dict.values())
dict_values.sort(reverse=True)

answer = 0
for i, x in enumerate(dict_values):
    answer += x * (9-i)
    
print(answer)