악곱 == 악성곱슬

해시, 그리디

---

해당 문제를 그리디로 접근한 정당성은 다음과 같다.

• 단어를 숫자로 바꾸어 더한 수의 최대값을 구하는데 단어의 개수가 최대 10개인 점 즉, AB + B * 9 를 할 때 더 높은자리의 수에 높은 숫자(9→8→7)순으로 부여해도 된다는 점. 만약 단어의 개수가 10개보다 크다면? 다른 방법을 사용해야 할 수도 있다.(생각해보진 않음)

탐색을 위한 시간을 절약하기 위해 dictionary 사용

import sys

def solution(words):
    answer = 0
    words_math = dict()
    for word in words:  # 최대 10개
        wn = len(word)
        for i in range(wn-1, -1, -1):  # 최대 8개
            if word[i] in words_math:   # O(1)
                words_math[word[i]] += 10**(wn - 1 - i)
            else:
                words_math[word[i]] = 10**(wn - 1 - i)

    words_math_list = list(words_math.items())
    words_math_list.sort(key=lambda x: x[1], reverse=True)

    cnt = 9
    for word_tuple in words_math_list:
        words_math[word_tuple[0]] = cnt
        cnt -= 1

    for word in words:
        tmp = 0
        wn = len(word)
        for i in range(wn-1, -1, -1):
            tmp += words_math[word[i]]*10**(wn-1-i)
        answer += tmp
    return answer

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    _words = list()
    for _ in range(N):
        _words.append(list(sys.stdin.readline().rstrip()))
    print(solution(_words))