[Baekjoon] 1339번 : 단어 수학

1. 문제

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

• 브루트포스, 그리디 문제

// 문제
민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 
각 단어는 알파벳 대문자로만 이루어져 있다. 
이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 
N개의 수를 합하는 문제이다. 
같은 알파벳은 같은 숫자로 바꿔야 하며, 
두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, 
A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 
두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

// 입력
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 
둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 
단어는 알파벳 대문자로만 이루어져있다. 
모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 
수의 최대 길이는 8이다. 
서로 다른 문자는 서로 다른 숫자를 나타낸다.

// 출력
첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

// 예제 입력 1 
2
AAA
AAA

// 예제 출력 1 
1998

// 예제 입력 2 
2
GCF
ACDEB

// 예제 출력 2 
99437

// 예제 입력 3 
10
A
B
C
D
E
F
G
H
I
J

// 예제 출력 3 
45

// 예제 입력 4 
2
AB
BA

// 예제 출력 4 
187

2. 핵심 아이디어

• 알파벳을 딕셔너리에 저장
• 자릿수 체크 후, 알맞은 값 매칭
• value만 가져와서 리스트에 내림차순 정렬
• 첫 수 부터 9를 곱함

3. Python 문제풀이

import sys
input = sys.stdin.readline

n = int(input())

al = []
dict = {}
arr = []

for i in range(n) :
  al.append(input().rstrip())

for i in range(n) :
  for j in range(len(al[i])) :
    if al[i][j] in dict :
      dict[al[i][j]] += 10 ** (len(al[i])-j-1)
    else :
      dict[al[i][j]] = 10 ** (len(al[i])-j-1)

for val in dict.values() :
  arr.append(val)

arr.sort(reverse = True)
sum = 0
p = 9

for i in arr :
  sum += p * i
  p -= 1

print(sum)

4. Java 문제풀이