[백준] 1339번 : 단어수학

안녕하세요. 개발자 빅광스 입니다. 오늘은 그리디 알고리즘 문제를 풀어보도록 하겠습니다.

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

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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

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

 

솔루션

저는 이 문제의 최적해 해를 찾기위해서 어제, 오늘 생각해본 결과 두가지 조건으로 최적해의 전략을 세웠습니다.

 

- 첫번째로는 자리수의 크기가 클수록 높은숫자를 가져야 최종 합이 커진다.

- 두번째로는 자리수가 같을때 문자의 수가 더 많으면 더 높은 가치를 가져야 최종합이 커집니다.

 

위 두개의 조건을 가지고 

각 자리수마다 가중치를 지정하여 더한다.

char[data[i]] = 10**(len(data) - i)

char[data[i]] += 10**(len(data) - i)

 

char라는 딕셔너리에 각각의 가중치를 지정하였기때문에 해당 가중치가 제일큰 알파벳을 제일 큰 숫자로 바꿔주면 됩니다.

 

다음은 해당 두개의 조건을 파이썬으로 구현하였습니다.

 

N = int(input()) # 단어의 개수를 입력
maxlen = 10 # 알파벳의 개수가 최대 10개 이기때문에 maxlen을 10으로 설정한다.
queue = [[] for _ in range(maxlen)] # idx 9 : 10번째 자리를 가지고 있는 문자열 리스트, 8 : 9번째 자리를 가지고 있는 문자열 리스트

charlist = []
char = dict() # 각 알파벳마다 가치를 넣는다.
for _ in range(N):
    data = input()
    charlist.append(data)
    for i in range(len(data)):
        if data[i] not in char:
            char[data[i]] = 10**(len(data) - i)
        else :
            char[data[i]] += 10**(len(data) - i)

minqueue = [] # 우선순위 큐로 넣을 수 있지만 sort 한번만 해주는게 더 시간복잡도가 빠르기 때문에 일반리스트로 지정
for i in char:
    minqueue.append([char[i], i])

minqueue.sort()
newchar = dict()
idx = 0
numlist = [9,8,7,6,5,4,3,2,1,0]

while minqueue: # 큐를 하나씩 빼서 newchar에 최종 번호를 지정한다.
    number , char = minqueue.pop()
    newchar[char] = str(numlist[idx])
    idx += 1

result = 0
for char in charlist:
    for i in newchar:
        char = char.replace(i,newchar[i]) # 지정된 번호로 replace해준다.
        
    result += int(char) # replace한 결과를 결과에 추가한다.
    
print(result)