[Greedy] 백준 1339번 “단어 수학” Python 풀이

문제 링크

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

풀이

• 해당 문제를 일반화하기 위해선, 각 알파벳의 자릿수를 기억해야합니다.
• 예를 들어, GCF + ACDEB 가 주어졌을 때, 각 알파벳의 자릿수를 별도로 저장합니다.
  • A는 만의 자릿수를 가지기 때문에 10000
  • C는 천의 자릿수와 십의 자릿수를 둘 다 가지기 때문에 1010
  • G는 백의 자릿수를 가지기 때문에 100
  • D는 백의 자릿수를 가지기 때문에 100
  • E는 십의 자릿수를 가지기 때문에 10
  • B는 일의 자릿수를 가지기 때문에 1
  • F도 일의 자릿수를 가지기 때문에 1
• 이렇게 알파벳의 자릿수를 별도로 저장한 뒤, 자릿수를 내림차순 정렬하고,
• 자릿수가 높은 순서대로 숫자를 감소시켜가며 곱셈을 진행합니다.
  • A = 10000 * 9 = 90000
  • C = 1010 * 8 = 8080
  • G = 100 * 7 = 700
  • D = 100 * 6 = 600
  • E = 10 * 5 = 50
  • B = 1 * 4 = 4
  • F = 1 * 3 = 3
• 이를 다 더해주면 99437이라는 값이 나오게 됩니다.
• 이때, (G, D)와 (B, F)처럼 같은 자릿수를 가지는 알파벳끼리는 누구한테 더 높은 숫자를 주는지는 중요하지 않습니다.
• 해당 문제에선, 각 알파벳이 가지는 숫자가 아닌, 주어진 단어의 합의 최대값을 물어봤기 때문입니다.

코드

import sys

# 알파벳의 자릿수 저장
dic = {}

# 단어의 개수
n = int(sys.stdin.readline())

# 알파벳에 따른 알파벳의 자릿수 저장
for _ in range(n):

    word = sys.stdin.readline().rstrip()

    for i in range(len(word)):
        # 해당 알파벳의 자릿수가 이미 있다면 자릿수를 추가
        if (word[i] in dic):
            dic[word[i]] += 10**(len(word)-i-1)
        # 해당 알파벳의 자릿수가 없다면 자릿수를 새롭게 저장
        else:
            dic[word[i]] = 10**(len(word)-i-1)

# 사전의 모든 값들을 결과 리스트에 추가한 뒤, 내림차순 정렬
result = []
for value in dic.values():
    result.append(value)
result.sort(reverse=True)

# 결과 리스트의 첫 번째 자릿수부터 순서대로 확인하며 숫자를 곱해주고, 
# 곱셈 결과를 최종 결과값에 덧셈
sum = 0 # 최종 결과값
num = 9 # 곱할 숫자
for value in result:
    sum += value * num
    num -= 1

# 결과값 출력
print(sum)