문제
요약
N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A~J가 자리수를 대신해서 쓰여있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고 각 자리수는 정확하게 알파벳 한 개이다. 0으로 시작하는 수는 없다. 가능한 수의 합 중 최댓값을 구하라.
분류
- 그리디
풀이
1. 내 풀이 (그리디 알고리즘)
여느 그리디 문제가 그렇듯이 발상이 어려웠다. 어떤 문자가 앞 자리에 있을수록 더 높은 수를 할당해야 했다. 우선순위를 어떻게 정하는가의 문제였다.
나는 우선순위 판별을 위해 자리수마다 가중치를 주는 방식을 택했다. 이를테면 다음과 같다.
- 자연수 123은 1 * 10^2 + 2 * 10^1 + 3 * 10^0 과 같다.
- 따라서 ABC 가 있다면 A에는 가중치 100, B에는 가중치 10, C에는 가중치 1을 줬다.
- 최종적으로 가장 높은 가중치를 얻은 문자에 대해 높은 수를 차례로 할당했다.
마지막으로 0이 첫 자리에 오는 경우를 고려해주었다.
import sys
input = sys.stdin.readline
n = int(input())
d = {}
start = set()
for _ in range(n):
string = input().rstrip()
start.add(string[0])
for i, s in enumerate(string):
try:
d[s] += 10 ** (len(string) - i - 1)
except:
d[s] = 10 ** (len(string) - i - 1)
#start에 없는 수 중 val 이 가장 작은 수가 0이 됨 (만약 a~j까지 모두 나왔을 때)
vs = list(d.items())
vs.sort(key = lambda x: -x[1])
if len(d) == 10:
for i in range(9, -1, -1):
if vs[i][0] not in start:
del vs[i]
break
ans = 0
num = 9
for alph, val in vs:
ans += num * val
num -= 1
print(ans)