단어 수학

문제

단어 수학문제는 N개의 단어로 이루어져있습니다. 각 단어는 알파벳 대문자로만 이루어져 있습니다. 각 알파벳 대문자를 0~9까지의 숫자중 하나로 치환후 N개의 수를 모두 더합니다. N개의 알파벳이 주어졌을때 최대값을 구하는 문제입니다.

제약조건

• N (1 <= N <= 10)
• 알파벳의 종류 최대 10개
• 단어의 최대 길이 8

풀이

자리수가 클수록 높은 번호를 가져야합니다. 처음에는 비트연산으로 접근했습니다. 각 자리수의 존재 여부만 체크하는 식으로 구했습니다.

예를 들어,
ABA
BA
의 경우 A는 101(2)를 가지게 되며 B의 경우 10(2)을 가지게 됩니다.
A의 경우가 더 크므로 A가 9를 가져가게 되고 B는 8을 가져가게됩니다.

하지만 이 경우는 다음과 같을때 문제가 됩니다.
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

A는 100(2) B는 11(2)를 가져가게 됩니다. 하지만 B가 9이고, A가 8인 경우가 더 이득입니다. 즉, 각 자리수의 존재여부만 고려하는것 아닌 각 자리수의 개수까지 따져 중요도를 따져야한다는 사실을 깨닫게 되었습니다.
즉, 위와 같은 경우에서 A는 백의 자리수가 1개이므로 100의 중요도를 가지고 B는 십의 자리수가 10개, 일의 자리수가 10개이므로 110의 중요도를 가집니다. B의 중요도가 높기때문에 9를 가지게 됩니다. 또한 여기서 십진수계산을 했으므로 B의 중요도인 110에 9를 곱하게 되면 B가 나타내는 값이 됩니다. A도 마찬가지로 800의 값을 가지게 됩니다. 따라서 990+800 = 1790의 값을 가지게 됩니다.

아래 코드는 다음과 같은 로직을 가집니다.
각 알파벳에 대한 가중치 계산하여 알파벳을 KEY로 하고 가중치를 VALUE로 하는 dict에 저장합니다.
가중치를 모두 구한 후에 KEY는 이제 결과와 관련이 없습니다. 따라서 KEY는 제외해서 정렬합니다. A가 100의 가중치, B가 100의 가중치를 가졌을때 A가 9을 가지던, B가 9를 가지던 결과는 같기 때문입니다. dict의 값만 뽑아 내림차순 정렬합니다.
정렬된 순으로 각각 9,8,7,6,5,4,3,2,1,0을 곱한뒤(N개를 곱함) 결과값에 더해갑니다. 반복문이 끝나면 결과값이 답이 됩니다.

코드

'''
Created by jun on 21/
'''

import collections
import sys

N = int(input())
words = [sys.stdin.readline().rstrip() for _ in range(N)]
dict = collections.defaultdict(int)

for word in words:
    for idx, w in enumerate(word[::-1]):
        dict[w] = dict[w] + 10 ** idx

nums = sorted(dict.values(), reverse=True)
res = 0

for idx, num in enumerate(nums):
    res += num * (9-idx)

print(res)

새로 알게된 사실

딕셔너리를 value를 기준으로 정렬하는법
가중치에 대한 생각