[Greedy] 백준 - 단어 수학 1339번

단어 수학 1339번

👏 key point

ABCDE + GCG를 예를 들어 살펴보면

자릿수가 제일 큰 수가 제일 큰 수인 9가 들어와야 하므로 A 는 9라는 것을 알 수 있다. 이런 식으로 자릿 수 순서대로 수를 배치할 수 있다.

하지만 C,G의 경우를 살펴보자.

C와 G중 어떤 값을 더 큰 값으로 정해야 할까? 뒤에 C와 G가 있는지 확인하고 뒤에 있는 C,G의 값 중 더 큰 값에 큰 숫자를 배정해주어야 한다. 즉, 자릿 수 순서대로 임의로 큰 수를 배정할 수는 없다. 그렇다면 이럴 경우 어떠한 방법이 있을까?

필자의 경우
ABCDE라는 문자를 배정받게 되면 dic 자료구조를 이용해
알파벳을 key로 설정 , 그리고 해당 알파벳의 위치에 해당하는 자릿수를 value값으로 지정하였다.

예를 들어 A의 경우 dic = {A: 10000 } 이 저장된다. 그리고 추가적인 A가 들어올 경우 value값을 + 해준다.

🎂 코드

n = int(input())

dic = {}

for _  in range(n):
    word = str(input())
    n = len(word)
    # 해당 알파벳 자릿수를 알아낸다.
    for i in range(n):
        # 해당 알파벳이 dic에 없다면
        if word[i] not in dic.keys():
            dic[word[i]] = pow(10,n-1-i)
        
        # 있다면 +
        else:
            dic[word[i]] += pow(10,n-1-i)
       

#coef는 계수를 나타낸다. 
coef = list(dic.values()) 

#구간들을 내림차순으로 저장
coef.sort(reverse=True)

cnt = 9
sum = 0

for c in coef:
    sum += cnt * c
    cnt -= 1

print(sum)