[백준] 1339 "단어 수학" -python

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

1339번: 단어 수학

 

 

알고리즘

 입력으로 주어진 모든 단어의 알파벳에 대해 자릿수를 구하고 그 합을 구한다.

예를 들어, 단어 ABCDA에서  A의 자릿수는 10001 ( A 관점에서 각 자리수에 A가 있는 부분에 1 아니면 0 )

모든 알파벳에 대하여 자릿수를 구한 뒤 더해서 저장해 둔다. 모든 단어에서 하나의 알파벳 관점으로 볼 때 최적해를 구하는 그리디 알고리즘이다.

 

# 단어수학
import sys, collections
N = int(sys.stdin.readline())

words = []
for _ in range(N):
    words.append(sys.stdin.readline().rstrip())

dic = collections.defaultdict(int)

for word in words: # 자리수 딕셔너리에 저장
    for w in range(len(word)):
        dic[word[w]] += 10 ** (len(word) - w - 1)

# 알파벳 가중치 저장
lst = sorted(dic, key=lambda x: dic[x], reverse=True)
digit = [i for i in range(9, -1, -1)][:len(lst)]
weight = dict(zip(lst, digit))

result = 0
for word in words:
    s = ""
    for w in word:
        s += str(weight[w])    
    result += int(s)

print(result)

 

느낀점

 처음에 길이가 긴 단어의 맨 처음 알파벳에 높은 가중치를 주는 방식으로 구현했더니 처리해야할 예외가 너무 많이 발생했다. 그리디라는 단어에 집착해서 방향을 잘못잡은것 같다.