[백준 - Gold IV] 단어 수학 - 1339

[백준 - Gold IV] 단어 수학 - 1339

 

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

 

 

문제 설명

 

1. 영어로 이루어진 N개의 단어가 제공

2. 영어 글자에 숫자(1~9)를 배정하고 합을 계산

3. 이때 숫자의 합이 최대가 되었을 때 해당 합을 출력

 

입력값 

N : 단어의 개수

S : N개의 단어 

 

출력값

res : 주어진 단어의 최댓값

 

핵심 로직 = 가중치

• 가장 큰 자릿수에 존재하는 글자부터 가장 큰 숫자 9 배정
• 자주 등장하는 글자도 포함해서 계산해야 함

 

풀이 코드

 

오답 코드

heapq, 우선순위 큐를 사용해서 자릿수에 대한 가중치만 생각한 코드, 자주 등장하는 글자를 체크하지 못한 것이 오답의 원인

import heapq

n = int(input())
s = [input() for _ in range(n)]
alpa = []
dic = {}
for i in s:
    l = len(i)
    for j,k in enumerate(i):
        heapq.heappush(alpa,(-10**(l-j),k))
i = 9
while alpa:
    a,c = heapq.heappop(alpa)
    if c not in dic:
        dic[c] = i
        i-=1

res = 0
for i in s :
    temp =''
    for j in i:
        temp+=str(dic[j])
    res+=int(temp)
print(res)

 

정답 코드

딕셔너리 사용을 통해 해당 글자의 자릿수와 빈도수를 체크

from collections import defaultdict

n = int(input())
s = [input() for _ in range(n)]
alpa = defaultdict(int)
for i in s:
    l = len(i)
    for j, char in enumerate(i):
        alpa[char] += 10 ** (l - j - 1) # 자릿수로 가중치 덧셈, 할당

sortAlpa = sorted(alpa.items(), key=lambda x: -x[1])
# print(sortAlpa)

dic = {}
num = 9
for char, _ in sortAlpa:
    dic[char] = num
    num -= 1

res = 0
for i in s:
    temp = ''
    for j in i:
        temp += str(dic[j])
    res += int(temp)

print(res)