[백준] 1339번: 단어 수학 (그리디)

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

1339번: 단어 수학

 

 

이 문제는 생각하기가 꽤 어려웠던 그리디 문제였다.

 

첫 번째 예제를 보면 

AAA + AAA 인데 A에 9를 주면 999+999 = 1998이 되어 합이 최대가 된다. 

A에 9가 아닌 숫자를 지정해주면 합이 최대가 되지 않는다.

 

두 번째 예제를 보면 (가장 많은 것을 알 수 있음)

ACDEB

+  GCF

 

여기서 우선 A에 9를 주고 C에 8을 준다.

D와 G에는 각각 7과 6을 준다. (순서는 상관없다)

C는 8이므로 E에는 그 다음 큰 숫자인 5를 지정해준다. 

딱 이 부분에서 어떤 문자에 대해 지정해 준 숫자를 기억해둬야 함을 캐치할 수 있다.

-> 딕셔너리를 사용하는 게 어떨까? 라는 생각이 든다.

마지막으로 B와 F에는 각각 4와 3을 준다. (역시 순서는 상관 없다)

 

결국 98754 + 683 = 99437이 되어 합이 최대가 된다.

 

세 번째 예제를 보면 

A 부터 J까지 총 10개의 서로 다른 문자에 배정된 숫자의 최대 합을 구해야한다.

A에 9를 주고, B에는 8, ... 이런식으로 J에 0을주고 나면 9 + 8 + 7 + ... + 1 + 0 = 45가 된다.

 

마지막 네 번째 예제를 보면

AB

BA 

 

역시 A에 9를 주고 B에 8을 준다면 98 + 89 = 187이 되어 최대가 된다.

 

그럼 이 문제를 어떻게 접근해야할까?

 

1. 먼저 알파벳을 딕셔너리에 저장한다.

   이 때, 단어의 길이에 따라 알파벳의 자릿수가 정해지므로 자릿수를 체크하여 그 자리에 맞는 값을 매칭시킨다.

   예를 들어 CBABD 같은 문자열이 있다고 가정해보자.

   {'A' : 100, 'B' : 1010, 'C' : 10000, 'D' : 1}

 

2. 매칭을 완료한 후에, dict의 value만 가져와서 리스트에 내림차순으로 정렬한다.

   그럼, 가장 큰 비율을 차지하는 것 부터 앞에 배치될 것이다.

   [10000, 1010, 100, 1]

 

3. 이 리스트의 첫 수부터 9, 8, 7, 차례대로 곱해주면 된다.

    이렇게 곱하면 가장 큰 비율을 차지하는 알파벳에 가장 큰 수를 부여하게 됨으로써 답을 도출해낼 수 있을 것이다.

 

import sys
input = sys.stdin.readline

n = int(input())

alpha = [] # 단어를 저장할 리스트
alpha_dict = {} # 단어 내의 알파벳별로 수를 저장할 딕셔너리
num_list = [] # 수를 저장할 리스트

for _ in range(n):
    alpha.append(input().rstrip())

for i in range(n): # 모든 단어에 대해서
    for j in range(len(alpha[i])): # 단어의 길이만큼 실행
        if alpha[i][j] in alpha_dict: # 단어의 알파벳이 이미 dict에 있으면
            alpha_dict[alpha[i][j]] += 10**(len(alpha[i])-j-1) # 자리에 맞게 추가 (1의 자리면 1)
        else: # 자리에 없으면 새로 추가 (10의 자리면 10)
            alpha_dict[alpha[i][j]] = 10**(len(alpha[i])-j-1)
            
for val in alpha_dict.values(): # dict에 저장된 수들을 모두 리스트에 추가
    num_list.append(val)

num_list.sort(reverse=True)

ans = 0
pows = 9

for num in num_list: # 첫 번째 부터 가장 큰 부분을 차지하므로 9를 곱해준다.
    ans += pows*num
    pows -= 1
# 내려갈수록 그 알파벳이 차지하는 비중이 적으므로 -1
print(ans)