[백준 알고리즘]1339 번 (Python)

문제 출처

www.acmicpc.net/problem/1339

1339번: 단어 수학

이 문제를 풀기위해 2가지 방법을 시도했는데

실패한 방법

첫 번 째 방식은 일단 알파벳을 읽은 후에 각 문장을 배열에 저장했었다. 그리고 그 배열의 길이 순으로 내림 차순정리한 후 알파벳 하나당 순서대로 9~0까지 할당해주고 더해주면 쉽게 답이 나올 것이라 생각했지만 역시 이렇게 쉽게 풀릴리가 없었다... 문제의 예시로 예를 들어 

GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면

ACDEB = 94654 , GCF = 783이 된다.

하지만 내 방식대로 하게되면 ACDEB = 98765 , GCF = 432이다. 이렇게 해서는 최댓값을 구할 수 없다.

처음에는 당연히 자리수가 큰순서대로 9부터 할당을 하니까 최댓값이 나올 줄 알았는데 문제는 두번 째 문장에서는 가능한 가장 큰 값을 부여할 수 없었다는 것이다.

 

성공한 방법

두 번 재 방식은 딕셔너리를 사용했다. 일단 배열을 내림차순 하는 것 까지는 동일하다.

(먼저 내림차순 안해도 풀 수 있었던 것 같긴하다.)

그 후 딕셔너리의 Key값을 각 알파벳으로 두고 Value 값에 알파벳의 각 자리수를 두었다.

예를들어 ABCDE라면 {A : 10000, B: 1000, C : 100 ........} 이런식으로..

그리고 동일한 알파벳이 있으면 그 키값에 해당하는 값에 해당 알파벳의 자릴수를 더해주었다.

ABCDA라면 {A : 10001....}이런식으로! 어차피 같은 알파벳이면 같은 숫자를 곱해주어야 하기 때문이다.

딕셔너리를 다 완성했으면 다시 리스트에 Value값들을 담고 내림차순 정렬한 후 9부터 차례대로 값들을 곱해하면서

더해주면 된다.

 

import sys

N = int(sys.stdin.readline())
ALP = list(sys.stdin.readline().strip() for x in range(N))
value = 9
ALPD = dict()
ALP.sort(key=lambda x: len(x), reverse=True)

for i in range(len(ALP)):
    for j in range(len(ALP[i])):
        if ALP[i][j] in ALPD:
            ALPD[ALP[i][j]] = ALPD[ALP[i][j]] + (10 ** (len(ALP[i]) - j - 1))
        else:
            ALPD[ALP[i][j]] = 10 ** (len(ALP[i]) - j - 1)

ALP.clear()
for val in ALPD.values() :
    ALP.append(val)
ALP.sort(reverse=True)
result = 0
for val in ALP:
    result += value*val
    value -=1
print(result)