[BAEKJOON/Python3] 백준 1339 단어 수학

www.acmicpc.net/problem/1339

1339번: 단어 수학

＊링크로 접속하여 문제를 확인할 수 있습니다.

 

대문자 알파벳으로 이루어진 N개의 단어가 있을 때 각 알파벳에 0~9까지의 수를 대입하여 수들의 합을 최대로 만드는 문제입니다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다는 조건이 있습니다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 됩니다.

 

처음에는 단순하게 단어들의 길이의 내림차순으로 정렬하여 가장 긴 단어부터 9, 8, 7 ~ 이런식으로 수를 부여해서 풀었습니다. 그러나 이 경우, 예를 들어 길이가 5인 단어에서는 1의 자리 수지만 길이가 4인 단어에서는 1000의 자리 수인 수가 존재하면 최댓값을 구할 수 없는 등의 문제가 발생하였습니다.

 

각 자리수의 값을 반영하여 해결하는 방법을 생각해보았습니다. 그리디 알고리즘을 이용하여 각 자리수 값을 중요도로 따져주어 중요도가 높은 수부터 9, 8, 7 이렇게 순차적으로 부여하였습니다. 딕셔너리에 각 알파벳의 중요도를 저장하고 (이 때 중요도는 GCF와 ACDEB라면 A의 중요도는 10000, C의 중요도는 1010과 같은 방식.) 중요도에 따라 정렬하여 숫자를 변환했습니다.

※그리디 알고리즘은 문제를 해결하는 과정에서 매 순간 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 방식입니다.

 

코드

 

단어의 개수를 입력받고 단어들을 words 리스트에 저장한 후 중요도를 저장할 important 딕셔너리를 만들었습니다. 이 딕셔너리에는 위에서 설명한 방식으로 단어들에 존재하는 알파벳들의 중요도를 저장하였습니다.

 

important 딕셔너리가 완성된 후, (알파벳, 중요도) 튜플 형태의 리스트로 변환하여 중요도에 따라 내림차순으로 정렬한 후 가장 중요도가 큰 알파벳부터 숫자를 순차적으로 부여하였습니다.

 

최종 완성되는 수들을 final 리스트에 저장하기 위해 리스트를 생성하고 각 단어의 각 알파벳을 순차적으로 문자열 형태로 순서대로 word_to_num 문자열에 저장하여 순서대로 나열하였고 각 단어의 모든 알파벳을 넣는 과정이 끝난 후에는 정수형으로 바꾸어 최종 숫자를 final에 저장하였습니다. 이렇게 완성된 최종 숫자들의 합을 sum 함수를 이용하여 구하고 출력했습니다.