[백준] 1339 단어 수학(Python)

문제 링크

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

1339번: 단어 수학

나의 풀이

• 이 문제는 구글링을 통해 풀이 방법을 참조했습니다.

1. 각 알파벳들이 단어의 어느 자릿수에 위치하는지 확인하고 이를 딕셔너리에 저장합니다.
   • ex) 'ADC'이면 A는 100, D는 10, C는 1을 딕셔너리에 'A' = 100, 'D' = 10, 'C' = 1로 저장하고, 다른 단어들에 대해서도 똑같이 각 자릿수를 딕셔너리에 더해줍니다.
2. 알파벳들이 어느 자릿수에 위치하는지 모두 검사를 한 뒤 만들어진 딕셔너리를 value를 기준으로 내림차순 정렬합니다.
3. 정렬된 딕셔너리를 처음부터 끝까지 탐색하며 value* 9-idx를 answer변수에 더해줍니다.

예제 input

2
GCF
ACDEB

• 1번 과정을 통해 {'G': 100, 'C': 1010, 'F': 1, 'A': 10000, 'D': 100, 'E': 10, 'B': 1} 딕셔너리가 만들어집니다.
• 2번 과정을 통해 [('A', 10000), ('C', 1010), ('G', 100), ('D', 100), ('E', 10), ('F', 1), ('B', 1)] 딕셔너리를 내림차순 정렬합니다.
• 3번 과정을 통해 answer변수에 10000*9, 1010*8..., 1*1을 더해줍니다. 

 

Code

from collections import defaultdict

words_num = int(input())

words = []

for _ in range(words_num):
    words.append(input().rstrip())

alphabets = defaultdict(int)

for word in words:
    for i in range(len(word)):
        alphabets[word[i]] += 1*(10**(len(word)-(i+1)))

sorted_alphabets = sorted(alphabets.items(), key = lambda x:-x[1])
answer = 0

for idx, alpha in enumerate(sorted_alphabets):
    answer += alpha[1] * (9-idx)
print(answer)

Git

https://github.com/youngh0/Algorithm/blob/master/greedy/boj_1339.py