1339: 단어 수학

단어 수학은 주어진 알파벳들에 대하여 각각의 알파벳을 0 ~ 9의 숫자로 하나씩 대응 시켰을 때 그 합이 최대가 되도록 하는 문제이다.

이해를 돕기 위해 한 가지 예시를 들어보면,

입력으로 ABCD와 EFG가 들어왔을 때 둘의 합을 최대로 만드는 경우를 생각해보자.

 

가장 먼저 떠오르는 방법은 위 그림처럼 알파벳에 값을 부여하는 방법이다.

즉 높은 자리수에 높은 숫자를 대응 시키면 최대에 가까운 값을 얻을 수 있을 것이다.

가장 높은 자리수를 가지고 있는 A에 가장 높은 숫자 9, 그 다음으로 높은 자리 수인 B, E에 각각 8과 7 ..

이런 식으로 숫자를 부여하도록 코드를 구현하고 제출했는데 오답 판정을 받았다.

 

무엇이 문제였을까.. 고민하고 찾아보던 도중 한 가지 예제에서 문제점을 확인 할 수 있었다.

만약 다음과 같이 알파벳이 들어온다면 어떨지 생각해보자.

---------------------------

ABB

BB

BB

BB

BB

BB

BB
BB

BB
BB

---------------------------

처음 우리가 떠올렸던 방법대로라면 A에 9를 넣고 B에 8을 넣었을 것이다.

계산해보면 988 + (88 * 9) = 1780 이 나온다.

하지만 다시 한 번 예제를 자세히 보면 B에 8을 넣으면 88을 9번 곱하지만, B에 9를 넣으면 99를 9번 곱하게 된다.

둘의 차이는 후자가 99 만큼 더 큰데, 다른 알파벳 ABB에서 A에 9를 넣고 B에 8을 넣은 것과 A에 8을 넣고 B에 9를 넣은 것은 전자가 89만큼 크다.

다시 말해서 B에 9를 넣고 A에 8을 넣은 것이 A에 9를 넣고 B에 8을 넣은 것보다 10만큼 더 큰 값을 가지게 된다.

결론적으로 높은 자리수부터 높은 숫자를 부여하는 것이 반드시 정답이 아니라는 것을 확인했다.

 

그렇다면 다른 방법으로 생각해 볼 수 있는 것은

자리수에 해당하는 누적 합을 계산해서 가장 큰 수부터 높은 숫자를 부여하는 방법이다.

같은 예제로 ABB가 있다면 A는 100만큼의 누적을, B는 11만큼의 누적을 부여하는 것이다.

이렇게 하면 다음으로 BB가 9번이 나오는 것만큼의 누적치를 반영할 수 있게 된다.

따라서 B는 11 * 9 = 99에 ABB에서의 누적 11을 더해서 110의 누적값을 가지게 된다.

반대로 A는 100만큼의 누적을 갖게 된다.

A의 누적치보다 B의 누적치가 더 크기 때문에 B에게 9를 A에게 8을 부여하는 방법이다.

 

이 방법으로 구현한 코드는 정답 판정을 받을 수 있었다.

문제를 풀 때 반례를 떠올리는 것이 중요하면서도 가장 어려운 것 같다.

 

import sys
 
n = int(input())
input_list = list()
 
for i in range(n):
  get_str = sys.stdin.readline().rstrip()
  input_list.append(get_str)
 
alpha_dict = dict()
for alpha_str in input_list:
  length = len(alpha_str)
 
  for alpha in alpha_str:
    if alpha in alpha_dict.keys():
      alpha_dict[alpha] += pow(10, length - 1)
    else:
      alpha_dict[alpha] = pow(10, length - 1)
    length -= 1
 
idx = 0
value_list = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
for count in sorted(alpha_dict.items(), key=lambda x:x[1], reverse=True):
  alpha_dict[count[0]] = value_list[idx]
  idx += 1
 
result = 0
for alpha in input_list:
  number = ''
  for idx in alpha:
    number += str(alpha_dict[idx])
 
  result += int(number)
 
print(result)