코딩테스트 스터디-1339 단어 수학2

ACMICPC 1339 단어 수학

백붕이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

설명

문제를 보자마자 그리디 알고리듬을 떠올렸다. 그리디 알고리듬은 3년전 글 참고
그래서 그냥 가장 자리수 큰 수부터 9 붙이면 되지 않을까 했는데…

AAA
BBx15(BB가 15개)

수가 이렇게 있으면 AAA가 999고 BB가 88이면 8815 + 999 = 2319가 되어
AAA가 888이고 BB가 99인 9915+888 = 2373보다 작게 된다.

그래서 처음에 생각한 것은 틀렸고…

발상의 전환을 해서 계산을 나중에 하면 되겠다.

• 만약 주어진 수가 ABC, ABCDE 2개가 있다 할 때…
• 이 두 수의 합을 풀어 쓰면 (Ax100+Bx10+C) + (Ax10000 + Bx1000 + Cx100 + Dx10 + E) 이렇게 할 수 있고..
• 이를 다시 묶으면 Ax10100+Bx1010+Cx101+Dx10+Ex1 이렇게 정리할 수 있다.
• 따라서 각 알파벳에 곱하는 수인 10101, 1010, 101, 10, 1을 따로 뺀 다음 가장 높은 순서대로 9,8,7,…을 부여하면 최대값이 나오지 않겠는가!

정답

아래는 파이썬으로 작성한 코드~

n = int(input())

dano = []

for i in range(n):
    dano.append(input())

jari = {}

# 각 알파벳이 몇 번씩 곱해지는지를 구하는 딕셔너리 만들어주기
# AAA+AAA 인 경우 A는 백/십/일의자리에 2번씩 등장하므로 222 이런식
for i in range(n):
    for j in range(len(dano[i])):
        if dano[i][j] in jari:
            jari[dano[i][j]] += 10 ** (len(dano[i])-j-1)
        else:
            jari[dano[i][j]] = 10 ** (len(dano[i])-j-1)

myotbon = []

for i in jari.values():
    myotbon.append(i)

# 위에서 구한 자리수를 리스트에 넣은 후 내림차순 정렬하고    
myotbon.sort(reverse = True)

answer = 0
sijak = 9

# 9부터 시작해서 제일 큰 것부터 곱해주고 더하면 끝!
for i in myotbon:
    answer += sijak * i
    sijak -= 1

print(answer)

후기

재밌는 문제라 올려보았다.
코딩테스트는 확실히 재치와 발상의 전환이 필요한 종목인 듯…머리가 10101이여야