[백준] 1339번 단어수학 - 파이썬(Python)

문제 (링크)

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

1339번: 단어 수학

 

나의 풀이

# 오답
import sys
input = sys.stdin.readline
words = []
word_dict = {}
n = int(input())
for _ in range(n):
    words.append(list(str(input().rstrip())))

words = sorted(words, key=lambda x:len(x), reverse=True)
longest_words = words[0]
i = 0
num = 9
while i < len(longest_words):
    if longest_words[i] not in word_dict:
        word_dict[longest_words[i]] = num
        num -= 1

    for j in range(1, len(words)):
        len_diff = len(longest_words) - len(words[j])
        if len_diff <= i:
            if words[j][i - len_diff] not in word_dict:
                word_dict[words[j][i - len_diff]] = num
                num -= 1

    i += 1

ans = 0
for word in words:
    word_to_num = ""
    for alpha in word:
        word_to_num += str(word_dict[alpha])
    
    ans += int(word_to_num)

print(ans)

코드 설명 및 풀이

처음 생각했던 방법은 가장 자리 수가 높이 있는 알파벳부터 차례대로 9부터 숫자를 부여하는 것이었다.

 

즉, 테스트케이스 2번에서 처럼 GCF와 ACDEB라는 문자열이 있으면

 

ACDEB + GCF로, 가장 자리수가 높은 A와 C에게 각각 9와 8을 부여하고, 나머지 DEB와 GCF 마찬가지로 자리수가 높은 순서대로 나머지 숫자들을 부여하는 것이었다.

 

즉, A, C = 9, 8, D, G = 7, 6, E = 5, B, F = 4, 3 이런식으로 부여하는 것이다.

 

이 방식은 주어진 테스트케이스에서는 모두 통과를 했지만 제출했을 때는 오답이 떴다.

 

반례를 찾아보니 만약 주어진 문자열이

10

ABB

BB

BB

BB

BB

BB

BB

BB

BB

BB

 

이라면, 내가 짠 코드에 따르면 가장 높은 자리의 A가 9를 부여받고 B가 8을 부여받게 된다.

 

결국, 988 + 88 + 88 + 88 + 88 + 88 + 88 + 88 + 88 + 88= 1780이 되는데 이는 최대값이 아니다.

 

만약 B가 9를 부여받고 A가 8을 부여받게 되면 899 + 99 + 99 + 99 + 99 + 99 + 99 + 99 + 99 + 99 = 1790이 되기 때문이다.

 

즉, 단순히 알파벳의 자리 수만 보고 숫자를 부여하는 것은 잘못된 접근법이었다.

 

n = int(input())
words = []
alpha_value = {}
for _ in range(n):
    words.append(list(input().rstrip()))

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

alpha_value = sorted(alpha_value.items(), key=lambda x: x[1], reverse=True)

alpha_to_num = {}

num = 9
for alpha in alpha_value:
    alpha_to_num[alpha[0]] = num
    num -= 1

ans = 0
for word in words:
    num = ""
    for alpha in word:
        num += str(alpha_to_num[alpha])
    
    ans += int(num)

print(ans)

해답은 각 알파벳의 모든 자릿수를 계산한 후 딕셔너리에 저장해 그 값을 토대로 숫자를 부여하는 것이다.

 

테스트케이스였던 GCF, ACDEB를 다시 살펴보자.

 

A은 6번째 자리에 한 번 와있다. 따라서 A의 자릿수의 합은 10^5(10000)이 된다.

 

B는 1번째 자리에 한 번 등장하기 때문에 B의 자릿수의 합은 10^0(1)이 된다.

 

C는 2번째 자리에 한 번, 5번째 자리에 한 번 등장하므로 10^1 + 10^4 = 1010이 된다.

 

이런 방식으로 등장하는 모든 알파벳에 자릿수의 합을 더해주고, 그 값이 큰 알파벳부터 큰 값을 부여해주면 된다.

 

첫 번째 풀이의 반례였던

10

ABB

BB

BB

BB

BB

BB

BB

BB

BB

BB

역시, A의 자릿수의 합은 10^2 = 100이고, B의 자릿수의 합은 10^1 * 10 + 10^0 * 10 = 110이므로 B가 9를, A가 8을 부여받아 올바른 답을 출력하게 된다.