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

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

1339번: 단어 수학

Greedy한 유형으로 핵심은 문자에 숫자를 대응하기 전에 모든 단어에 같은 알파벳이 얼마나 있는지가 중요하다.

처음에는 가장 왼쪽에 있는 알파벳부터 9를 대입하는 방식을 고안했는데 바로 틀렸다.

반례를 이러하다.

ABBBBBB
B
BBB.....위으 경우와 같이 특정 개수이상 B가 계속 나오는 경우에는 A보다 B의 숫자가 더 커야지 최댓값이 되기 때문에 문자와 숫자를 대응하기 전에 자릿수를 고려하여 문자들을 모두 더해주어야한다.위의 경우 A:10   B:1+1+1+1+1+1+1+1+1+...+1 이렇게 될 것이다.위의 결과를 역순으로 정렬하여 숫자가 큰 곳부터 9를 대입해주면 된다.코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
n = int(input())
words = []
alpha_info = {}
for _ in range(n):
  words.append(input().rstrip())
for i in words:
  for j in range(len(i)):
    length = len(i)-j-1
    if i[j] not in alpha_info:
      alpha_info[i[j]] = 10**length
      continue
    alpha_info[i[j]] += 10**length
alpha_info = list(alpha_info.values())
alpha_info.sort(reverse=True)
ans = 0
idx = 0
for i in range(9,9-len(alpha_info),-1):
  ans += alpha_info[idx] * i
  idx += 1
print(ans)

 

 

 

 

처음에 높은 자릿수부터 그냥 9를 대입하여 하나씩 줄여갔는데 그러기엔 어쩐지 골드 4치고 너무 쉽게 풀린다 했다.

바로 틀렸습니다...ㅋㅋ

다행이 반례를 바로 생각해서 고쳤다.