[python3] 백준 1339 풀이 ( 단어 수학, 그리디 )

이 문제는 상당히 헤맸다. 결국 1시간내에 풀지 못해서 질문을 찾다보니 좋은 접근 방법이 있어서 그걸 토대로 푸니 금방 풀렸다.

길이가 최대 8인 문자열이 최대 10개가 주어진다. 각 알파벳은 숫자를 의미하는데 숫자를 대입하여 모든 문자열의 총합을 구하면 된다.
예를 들어 AB + A의 최대값은 98+9 = 117로 나타낼 수 있다. 그럼 간단한 규칙을 찾아낼 수 있다.

1. 가장 앞에 있는 문자열일수록 큰수를 대입해야한다.
2. 많이 나올수록 큰수를 대입해야한다.
그런데 이렇게 정리하면 삽질을 하게 된다. 한마디로 짧게 생각하면 스스로 함정에 빠지는 거다.

그냥 간단하게
AB -> A*10+B*1,
B-> B*1
AB+B -> A*10 + B*2 가 된다. 따라서 이걸 그대로 해주면 어떤 값이 가장 크게 나오는지 한번에 확인할 수 있다.

그럼 로직은 아래와 같다.

1. 단어를 확인하며 각 알파벳이 어느정도로 나오는지 파악한다.
2. 가장 큰 값을 가진 알파벳부터 순서대로 큰 값을 대입한다.(9,8,7,.....0)
3. 알파벳별 대입값을 토대로 총합을 구한다.

N = int(input())

words = []
dict = {}
for i in range(N):
    word = list(input())
    N = len(word)-1
    for w in word:
        if w not in dict:
            dict[w] = 10**N
        else:
            dict[w] += 10**N
        N -= 1
    words.append(word)
tmp = []
for k in dict:
    tmp.append([dict[k], k])
tmp.sort(key=lambda x: (-x[0]))
N = 9
newDict = {}
for t in tmp:
    score, alpha = t
    newDict[alpha] = N
    N -= 1
total = 0
for word in words:
    s = ""
    for w in word:
        s += str(newDict[w])
    total += int(s)
print(total)