[Python]백준 1339번/단어수학/greedy

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

1339번: 단어 수학

⚡️ 문제 설명

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다.

이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다.

같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때,

A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

 

⚡️ 해결 방법

이 입력을 예시로 설명해보면

2
GCF
ACDEB

 

1. dictionary에 각 자릿수를 10의 n승으로 저장

for word in words:
    length=len(word)
    for idx,ele in enumerate(word):
        if(ele in dic):
            dic[ele] += pow(10,length-idx-1)
        else:
            dic[ele] = pow(10,length-idx-1)

2. 이 dictionary를 value 값을 기준으로 정렬한다.

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

3. 각 자리에 9부터 차례로 곱해준 것을 결과에 더한다.

num=9
result=0
for d in dic:
    result += num*d[1]
    num -=1

⚡️ 코드

import sys

input = sys.stdin.readline
n = int(input())
words = []
for _ in range(n):
    words.append(input().strip())

dic=dict()
for word in words:
    length=len(word)
    for idx,ele in enumerate(word):
        if(ele in dic):
            dic[ele] += pow(10,length-idx-1)
        else:
            dic[ele] = pow(10,length-idx-1)

# dic을 value기준으로 정렬
dic=sorted(dic.items(),key=lambda x:x[1], reverse=True)

num=9
result=0
for d in dic:
    result += num*d[1]
    num -=1
print(result)