[백준] 1339 단어 수학

문제 링크

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

사용 알고리즘

• 그리디

풀이

단어들에 등장하는 알파벳에 각각 숫자를 대입해서 반환된 값의 합의 최대를 구하는 문제이다.

 

이를 구하기 위해서는 등장하는 각 알파벳 별로 모든 단어에서 해당 알파벳이 위치한 자리가 큰 순서대로 숫자를 할당해주면 된다.

 

예제

입력

2
GCF
ACDEB

 

위의 예제에서 등장하는 알파벳은 (A, B, C, D, E, F, G)이다.

 

알파벳이 등장하는 자리에 따라 가중치를 더 크게 주어야 하기 때문에 모든 단어들에 0을 패딩해 자리수를 맞춰주자.

index	0	1	2	3	4
S[0]	0	0	G	C	F
S[1]	A	C	D	E	B

 

이와 같은 상태에서 자리수별로 가중치를 주게 된다면 아래 표와 같이 되고, 가중치가 높은 순서대로 숫자를 할당해주면 된다.

알파벳	가중치	할당된 숫자
A	10,000	9
C	1,010	8
D	100	7
G	100	6
E	10	5
B	1	4
F	1	3

 

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

n = int(input())
words = [input().zfill(8) for _ in range(n)]

d = dict()
for w in words:
    for i in range(len(w)):
        if w[i] == '0': continue

        if w[i] not in d: d[w[i]] = 0
        d[w[i]] += 10 ** (8 - i - 1)

d = sorted([[x[0], x[1]] for x in d.items()], key=lambda x: x[1])
k = dict()
for i in range(9, 10 - len(d) - 1, -1):
    k[d.pop()[0]] = i

res = 0
for w in words:
    t = 0
    for c in w:
        if c not in k: continue
        t *= 10
        t += k[c]
    res += t

print(res)