단어 수학

풀이

 처음에는 단순히 앞에 있는 문자부터 순서대로 높은 숫자를 지정해주는 단순한 그리드 알고리즘으로 인식했다. 하지만 그렇게 단순한 문제가 아니었다. 아래 예시를 보자.

A에 9를 지정하는 경우
A B C
9 8 7

B C A
8 7 9

result = 1866

B에 9를 지정
A B C
8 9 7

B C A
9 7 8

result = 1875

A와 B 중 9와 8을 할당해야 하는데 아래 자리 알파벳의 배치에 따라 A와 B에 할당돼야 하는 값이 달라진다. 위 예시에서는 2개를 비교했지만, n이 조금만 커져도 이를 비교하기에는 복잡하고 어렵다. 아마 이렇게 풀면 for 문을 굉장히 많이 중첩해서 시간초과가 날 수도 있을 거라 생각했다.
따라서 관점을 바꿔서 각각의 단어에 대해서 생각할 것이 아니라 모든 단어에서 알파벳이 어느 위치에 등장하고 그것이 10의 몇 제곱을 나타내는 지를 구해서 모두 더했다. 그런 뒤 이를 내림차순 정렬해서 큰 값부터 9, 8, 7,.. 계수 값을 할당해줘서 문제를 풀었다.

n = int(input())
data = []
for i in range(n):
    data.append(input())
alpha = [0] * 26

for i in data:
    length = len(i)
    x = 1
    for j in range(length-1, -1, -1):
        alpha[ord(i[j]) - ord('A')] += x
        x *= 10

alpha.sort(reverse=True)
num = 9
result = 0
for i in alpha:
    result += i*num
    num -= 1
print(result)

시간복잡도 : O(n)