[Python] 백준 / gold / 1339번 (단어 수학)

문제 링크 : https://www.acmicpc.net/problem/1339

그리디 알고리즘 문제이다.
그리디적 논리를 생각하기엔 어렵지 않지만 구현이 까다로웠다.

알파벳에 숫자를 매기는 순서

1. 그 알파벳이 등장하는 최고자리 숫자가 큰 경우부터
2. 그게 같은 경우에는 그 아랫자리 숫자 체크

예를들어, ABC, DEBGH 가 있을 경우
-> D의 최고 자리숫자는 10000의 자리, E의 최고 자리숫자는 1000의 자리이다.
따라서 D에 9를, E에 8을 부여하는 것은 명확하다.
100의 자리숫자는 A와 B가 등장한다. 하지만 B는 10의자리 숫자에도 등장한다.
따라서 A가 아닌 B에 7을 부여하는 것이 옳다.

이 논리를 구현으로 옮긴다면 [점수부여] 방식을 사용할 수 있을 것 같다.
복잡한 상황을 가정해보자. 1000000의 자리에서 A,B가 등장 했고, 100000의 자리에서도 A,B가 등장 했고, 그 다음 그다음.. 계속 겹친다면 안 겹칠때까지 찾을것인가 ? 그건 비효율적이다.

3개의 단어 AXXXX, AXX, AX가 주어졌을 때
A의 점수를 10110 으로 부여하고, 다른 알파벳도 같은 방식으로 부여하면 합리적인 숫자 매기기가 가능해질 것이다.

정답 코드

import sys
N = int(input())

words = [sys.stdin.readline().strip() for _ in range(N)]

# { A:10000, B:1, G:100, ..}
alpha = dict()

for word in words:
    for i in range(len(word)):
        if not word[i] in alpha:
            alpha[word[i]] = 10**(len(word)-i-1)
        else:
            alpha[word[i]] += 10**(len(word)-i-1)

result = []
for a in alpha:
    result.append((a,alpha[a]))

result.sort(key=lambda x:x[1],reverse=True)

num = 9
for x, y in result:
    alpha[x] = num
    num -= 1

answer = 0
for word in words:
    temp = ""
    for w in word:
        temp += str(alpha[w])
    answer += int(temp)

print(answer)