[백준 1339] 단어 수학 (python)

https://www.acmicpc.net/problem/1339

1339번: 단어 수학

단어 수학 문제

알파벳으로 이루어진 문자를 숫자로 변환해서 더했을 때 최대값을 구하는 문제

완전 탐색으로 시도했다가 당연하게도 시간초과가 나서 고민하다가 다른 분에게서 아이디어를 얻어 해결

내가 틀린 코드

import sys
from itertools import permutations
N = int(sys.stdin.readline())
S = [0]*N
alpha = []
temp = {}
result = float('-inf')
for value in range(N):
    S[value] = sys.stdin.readline().strip()
    for a in S[value]:
        if a not in alpha:
            alpha.append(a) 
            
num = [i for i in range(9,(9-len(alpha)),-1)]
for m in permutations(num,len(alpha)): # 순열을 통한 완전탐색
    for i in range(len(num)):
        temp[alpha[i]] = m[i]
    sums = 0
    for j in S:
        letter = ''
        for k in j:
            letter += str(temp[k])
        sums += int(letter)
    result = max(result,sums)
print(result)

정답 코드

import sys
N = int(sys.stdin.readline())
S = [sys.stdin.readline().strip() for _ in range(N)]
words = {} # 단어별 값을 지정
for s in S: 
    x = len(s)-1 # 10의 제곱을 해줄 값
    for i in s :
        if i in words:
            words[i] += 10**x # 있으면 x만큼 제곱한걸 더하고
        else :
            words[i] = 10**x # 없으면 x만큼 제곱해서 넣자
        x -= 1

words_sort = sorted(words.values(),reverse=True) # 딕셔너리의 value만 내림차순으로 가져오자
result = 0
num = 9
for k in words_sort:
    result += k * num # 내림차순 한거에 9부터 하나씩 곱해서 더해주자
    num -= 1
print(result)

📌 문제 접근 포인트

1. 각 알파벳에 숫자를 지정해줄 방법을 생각해보자. 가장 대표적으로는 하나씩 지정해서 완전 탐색 하는 방법이 있다.
2. 완전 탐색하면 기본적으로 N의 숫자가 10이 되면 10!*10의 연산이 기본적으로 들어가버려서 2초안에 들어오기 불가능하다.
3. 다른 방법을 생각해보자. 서로 자릿수가 같거나 다른 알파벳을 숫자로 더해주는 과정을 거쳐간다 → 그렇다면 알파벳의 각각의 자릿수만큼 더한걸 모아보면 어떨까?
4. 예를들어 ABC와 ZACYX, CCB 라는 알파벳을 변환해서 지정해준다고 해보자. 3번에서 말한걸 이용하면 다음과 같은 과정으로 계산할 수 있다.

ABC에서 A : 백의 자리수니까 100, B : 십의 자리수니까 10, C : 일의 자리수니까 1을 할당해주자.
ZACYX : Z : 만의 자리수니까 10000,  A: 천의 자리수니까 1000, C : 백의 자리수니까 100, Y : 십의 자리수니까 10, X : 일의 자리수니까 1을 할당해주자
CCB : C: 백의 자리수니까 100, C : 십의 자리수니까 10, B : 일의 자리수니까 1

이제 각각의 알파벳에 해당되는 숫자를 모두 더해보자
A = 100+ 1000 = 1100
B = 10 + 1 = 11
C = 1 + 100 + 100 + 10 = 211
X = 1
Y = 10
Z = 10000

5. 이 숫자들을 어떻게 활용할 수 있을까? → 알파벳에 0~9까지 숫자를 할당해주니까, 가장 큰 자리수를 갖는 애부터 제일 높은 숫자를 하나씩 지정해줘서 더하면 최대값의 결과를 얻을 수 있다.
Z(9) = 90000, A(8) = 8800, C(7) = 1477, B(6) = 66, Y(5) = 50, X(4) = 4
이 숫자들을 다 더하면 최대 값인 100,397을 얻을 수 있다.