[Greedy] 백준 1339 : 단어수학 - 파이썬 Python

 

 

생각하기

N개의 단어가 주어졌을 때 가장 큰 자리수를 가진 알파벳에 가장 큰수를 순서대로 주면 될거 같다고 생각했다

가중치가 있으면 좋다고 생각을 했다

각 자리수에 따라 10단위의 가중치를 주기로 했다

• 5번째 자리 : 10000
• 4번째 자리 : 1000
• 3번째 자리 : 100
• 2번째 자리 : 10
• 1번째 자리 : 1

각각의 알파벳의 자리수 위치에 따라 각 자리수에 해당하는 가중치를 더한다.

구현하기

가중치를 더할 때, 알파벳 딕셔너리에 넣기위해 인덱스(숫자)화 해야 했다

물론 그냥 문자 그대로 딕셔너리에 넣어도 되지만 접근을 쉽게 하기 위해 숫자화 해주었다

• ord('A') : 'A' character를 ascill코드로 바꾸어 준다

alpha_score 이라는 딕셔너리에 각 알파벳에 대한 가중치 값을 지속적으로 더해준다

alpha_score을 추후에 value값을 기준으로 내림차순 sort를 진행한 후에 

9부터 차례로 높은 알파벳의 가중치에 곱해주면서 더해나간다.

 

 

import sys
input = sys.stdin.readline

N = int(input())

alpha_score=dict()

for i in range(26):
    alpha = chr(ord('A') + i)
    alpha_score[alpha] = 0


data =[]

score = [1]
for i in range(1, 8):
    score.append(score[i-1]*10)



max_len = 0
for i in range(N):
    data.append(list(map(str, input().strip())))
    data[i].reverse()
    for j in range(0, len(data[i])):
        alpha_score[data[i][j]] += score[j]


sorted_alpha_score = sorted(alpha_score.items(), key=lambda x : x[1], reverse=True, )
        

sum = 0
for i in range(0, 9):
    sum += sorted_alpha_score[i][1]*(9-i)

print(sum)