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

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개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

---

풀이 과정

단어에 등장하는 알파벳을 0~9중의 숫자 중 하나와 매치한다. (단, 수의 중복은 없다. A에 9를 썼으면 B에 9 사용불가)

ABCDE이면 자리수로 봤을 때 A가 가장 큰 비중을 차지하므로 ( 10^4 = 10000 ) A에 9를 매칭시키는 것이 좋을 것이다.

 

이렇게 가장 큰 비율을 차지하는 알파벳에 최대의 수를 부여해야 하므로

그리디 알고리즘으로 해석할 수 있다.

이 문제는 그리디 알고리즘 중에서도 꽤 까다로운 문제였다.

 

1. 먼저, 알파벳을 딕셔너리에 저장한다.
   이 때, 단어의 길이에 따라 알파벳의 자릿수가 정해지므로 자릿수를 체크하여 그 자리에 맞는 값을 매칭시킨다.
   { 'A' : 100, 'B' : 1010, 'C': 1 ... }
2. 매칭을 완료한 후에, dict의 value만 가져와서 리스트에 내림차순으로 정렬한다.
   그럼, 가장 큰 비율을 차지하는 것 부터 앞에 등장할 것이다.
   [11000, 10000, 1000, 100 ... ]
   
   
3. 이 리스트의 첫 수 부터 9를 곱하면 된다.
   그 다음 8, 7, ....
   이렇게 곱하면 가장 큰 비율을 차지하는 알파벳에 가장 큰 수를 부여하게 됨으로써 답을 도출해 낼 수 있을 것이다.

↓ 설명과 함께 첨부한 코드 ↓

import sys

n = int(sys.stdin.readline())

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

for i in range(n): # 단어를 입력받음
    alpha.append(sys.stdin.readline().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에 저장된 수들을 모두 리스트에 추가
    numList.append(val)

numList.sort(reverse=True) # 수들을 내림차순 정렬

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

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !