[백준-골드4] 1339번 단어 수학 (그리디, 파이썬)

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

1339번: 단어 수학

 

<내 코드>

- 입력으로 n개의 단어가 알파벳으로 주어졌을때, 알파벳에 숫자를 부여해서 수의 합을 최대로 하는 문제이다.

- 입력으로 받은 words리스트를 순회하면서, 각 word의 자릿수를 파악하고 값으로 변환하여 딕셔너리에 넣어준다.

- 이 때 알파벳이 딕셔너리에 없다면 10**m (여기서 m은 자릿수)를 넣어주고, 

   이미 딕셔너리에 알파벳이 있다면, 10**m을 더해준다.

- 그리고 다음 순회를 위해 자릿수를 감소해준다 m = m - 1

- 모든 단어에 대한 순회가 끝나면 value_list에 딕셔너리의 값을 기준으로 내림차순으로 정렬한다.

- num = 9로 가장 큰 수로 시작하고 value_list를 돌면서 ans에 값을 더해주고, num을 감소시키면서 다음 큰 수를 곱해준다.

 

n = int(input())
words = []
for _ in range(n):
    words.append(input())
    
dic = {}
for word in words:
    m = len(word) - 1 #자릿수를 나타냄
    for i in range(len(word)):
        if word[i] not in dic:
            dic[word[i]] = 10**m
        else:
            dic[word[i]] += 10**m
        m -=1

value_list = sorted(dic.values(), reverse = True)

ans = 0
num = 9
for val in value_list:
    ans += val*num
    num-=1
    
print(ans)

 

[예시 및 반례]

'''
<<입력>>
2
GCF
ACDEB

<<출력>>
dic = {'G': 100, 'C': 1010, 'F': 1, 'A': 10000, 'D': 100, 'E': 10, 'B': 1}
value_list = [10000, 1010, 100, 100, 10, 1, 1]

<<정답>>
99437
'''

'''
<<입력>>
10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

<<출력>>
dic = {'A': 100, 'B': 110}
value_list = [110, 100]

<<정답>>
1790

'''