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

문제 링크

알고리즘

• 그리디 알고리즘
• 브루투포스 알고리즘

풀이

각 문자마다 (자릿수 - 1) ** 10을 제곱해서 딕셔너리에 저장한다.
예를 들어 BCE + ACDEB 가 주어지면

{
A: 10000
B: 100 + 1
C: 1000 + 10 
D: 100
E: 10 + 1
}

이렇게 정리할 수 있다.

이제 각 Value 들을 리스트에 모아서 큰 값 -> 작은 값 순으로 정렬한다.
위의 예제에서는 [10000, 1010, 101, 100, 11] 순으로 정렬할 수 있다.
그리고 [9,8,7,6,5,4,3,2,1,0] 의 각 인덱스에 대응하는 값끼리 곱해서 더하면 정답이 나온다.

코드

import sys

input = sys.stdin.readline

N = int(input())

# N개의 단어를 리스트에 저장
words = [input().strip() for _ in range(N)]

dic = {}  # 단어의 크기를 저장할 딕셔너리
nums = list(range(9, -1, -1))  # 9에서 0까지
res = 0

# 단어가 담긴 리스트를 순회하면서 딕셔너리에 크기를 저장
for word in words:
    for i in range(len(word)):
        try:
            dic[word[-(i + 1)]] += 10**i
        except:
            dic[word[-(i + 1)]] = 10**i

# 큰 값 -> 작은 값 순으로 정렬
lst = sorted([dic[x] for x in dic], reverse=True)

# 제일 큰 값부터 차례대로 곱해서 res에 더하기
for i in range(len(lst)):
    res += lst[i] * nums[i]

print(res)