문제
민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.
단어 수학 문제는 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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.
출력
첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.
예제 입력 1
2
AAA
AAA
예제 출력 1
1998
예제 입력 2
2
GCF
ACDEB
예제 출력 2
99437
예제 입력 3
10
A
B
C
D
E
F
G
H
I
J
예제 출력 3
45
예제 입력 4
2
AB
BA
예제 출력 4
187
문제 해결 과정
합이 최대가 되려면 자리수가 젤 큰 문자가 9가 되어야한다. 그렇다면 두 개의 문자열에 같은 문자가 반복되서 헷갈릴 수도 있다고 생각했다.
나는 처음에 각 알파벳 대문자들이 위치하고 있는 자리 수가 젤 크면 클수록, 9부터 숫자를 배정하면 된다고 생각했다.
예를 들어, 'ABCD', 'BCDEF' 두 개의 문자열이 있다고 가정해보자.
A는 뒤에서 index를 계산했을 때 3, B는 2, C는 1, D는 0이 된다. 문자열이 'ABCD' 하나만 존재한다면 이대로 끝이곘지만 'BCDEF' 때문에 자리 수가 갱신된다.
B는 4, C는 3, D는 2, E는 1, F는 0이 된다. 이렇게 되면 결과적으로 B = 9, A = 8, C = 7, D = 6, E = 5, F = 4 가 된다. (A와 C는 index, 즉 위치가 같지만 A가 먼저 들어와서 그냥 더 높은 수 배정)
따라서 코드는 다음과 같았다.
N = int(input())
dic = {}
char_list = []
for _ in range(N) :
st = input()
char_list.append(st)
st = list(st)
for i in range(len(st)) :
if st[i] in dic.keys() :
if dic[st[i]] < len(st)-1-i :
dic[st[i]] = len(st)-1-i
else :
dic[st[i]] = len(st)-1-i
sorted_list = sorted(dic.items(), key=lambda x:x[1])
num = 9
while(1) :
item = sorted_list.pop()
dic[item[0]] = num
num -= 1
if len(sorted_list) == 0 : break
cnt = 0
ch = ''
for char in char_list :
for c in char :
c = str(dic[c])
ch += c
cnt += int(ch)
ch = ''
print(cnt)이렇게 하니 해결하지 못했는데, 아마 같은 자리 수에 있는 수들끼리 우선 순위를 정하지 못해서 틀린 것 같았다. (위를 예시로 들면 A와 C)
그러다 하나의 블로그를 참고 했는데, 자리 수를 적용해야하는 건 맞지만 나처럼 역 인덱스가 아닌 두 번째 자리 수면 10을, 세 번째 자리 수면 100을 딕셔너리에 더해서 우선순위를 정했다.
위와 같은 예시를 다시 들면, 'ABCD', 'BCDEF' 두 문자열이 있다.
A에는 처음에 1000이, B에는 100이 C에는 10이, D에는 1이 된다. 그 다음에 B에는 10000이, C에는 1000 등등 이런 식으로 딕셔너리[알파벳] += 10의 자리수 제곱이 된다.
이렇게 해결을 하면 같은 자리 수에 있어 우선 순위를 해결하지 못했던 부분을 해결할 수 있다.
최종 코드
N = int(input())
dic = {}
char_list = []
for _ in range(N) :
st = input()
char_list.append(st)
st = list(st)
for i in range(len(st)) :
if st[i] in dic.keys() :
dic[st[i]] += 10**(len(st)-1-i)
else :
dic[st[i]] = 10**(len(st)-1-i)
sorted_list = sorted(dic.items(), key=lambda x:x[1])
num = 9
while(1) :
item = sorted_list.pop()
dic[item[0]] = num
num -= 1
if len(sorted_list) == 0 : break
cnt = 0
ch = ''
for char in char_list :
for c in char :
c = str(dic[c])
ch += c
cnt += int(ch)
ch = ''
print(cnt)