문제 출처
1339번: 단어 수학
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대
www.acmicpc.net
이 문제를 풀기위해 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)
