[백준 - Python] 1339. 단어수학 (그리디)

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

1339번: 단어 수학

 

코드

import sys
n = int(sys.stdin.readline())
str = [sys.stdin.readline().strip() for _ in range(n)]
words = {}

for s in str:
    x = len(s)-1  # 지수로 올라갈 값
    for i in s:
        if i in words:
            words[i] += 10**x
        else:
            words[i] = 10**x
        x -= 1

_words = sorted(words.values(), reverse=True) # 딕셔너리의 value 값을 기준으로 내림차순

result = 0
n = 9
for k in _words:
    result += k * n
    n -= 1

print(result)

 

문제 이해는 쉬웠는데, 구현을 위한 아이디어를 생각하기 많이 어려웠던 문제였다.

 

길이가 긴 단어 순으로 정렬을 하여 자리 수가 큰 수부터 차례대로 가장 큰 9부터 할당을 해야겠다는 생각을 했고,

알파벳과 숫자 사이의 대응 관계를 딕셔너리로 관리하고자 했는데,

다음 큰 숫자를 할당할 알파벳을 선정하는 코드를 구현하는데에 어려움이 있었고 결국 통과를 못시켰다.

그래서 다른 분들의 풀이를 참고했다.

 

대다수의 사람들이 사용한 아이디어는 이렇다.

특정 알파벳이 등장하는 자리 수에 맞게 숫자를 할당해주고

해당 알파벳이 다른 단어에서 등장하면, 똑같이 등장하는 자리 수에 맞는 숫자를 추가로 더해준다.

 

할당이 되는 숫자는 추후에 변환된 수의 합을 수월하게 구하기 위해서

x 자리 수이면 10^x 만큼의 숫자를 할당해준다.

 

주어진 단어에 포함된 알파벳 전부를

모두 등장한 만큼 숫자를 할당해 준 뒤에는

딕셔너리의 value 값을 기준으로 내림차순으로 정렬하고

가장 큰 수인 9부터 차례대로 곱해서 더해주면 수의 합을 최대로 만들 수 있다.

 

이렇게 까다로운 아이디어를 요구하는 문제들은

문제를 많이 풀어보고 복습을 잘하면서

데이터를 많이 쌓아 실력을 키우는 수밖에 없는 것 같다.