백준 1339번 파이썬 풀이: 단어 수학

백준 1339번 단어 수학

 

알고리즘 분류: 그리디 알고리즘, 백트래킹

 

링크: www.acmicpc.net/problem/1339

 

1339번: 단어 수학

문제

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

단어 수학 문제는 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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

 

 

문제 파악

 

이 문제는 주어지는 알파벳을 숫자로 바꿔서 더했을 때 최대값이 나오게 하는 문제이다.

 

같은 알파벳은 같은 숫자여야하고 서로 다른 알파벳이 같은 숫자를 가지면 안된다.

 

무슨말인지 좀 더 이해하기 위해서 예제를 이용해보자면

 

AAA + AAA가 최대가 되기 위해서는 A가 9면된다.

 

GCF + ACDEB가 최대가 되기 위해서는 자리수가 높은 A, C, G, D 이런순으로 높은 숫자를 가지면 된다.

 

이를 일반화 하기 위해서

 

A는 만의자리 수 이기 때문에 10000 값을 주고

C는 천의자리 수와 십의자리 수를 둘 다 가지기 때문에 1010 값을 준다.

G는 백의자리 수를 가지기 때문에 100

D는 백의자리 수를 가지기 때문에 100

E는 십의자리 수를 가지기 때문에 10

B는 일의자리 수를 가지기 때문에 1

F도 일의자리 수를 가지기 때문에 1을 준다.

 

이렇게 정렬을 해놓고 값이 높은 알파벳 순서대로 9부터 숫자를 준다.

 

A = 10000 * 9 = 90000

C = 1010 * 8 = 8080

G = 100 * 7 = 700

D = 100 * 6 = 600

E = 10 * 5 = 50

B = 1 * 4 = 4

F = 1 * 3 = 3

 

이를 다 더해주면 99437이라는 값이 나오게 되는 원리이다.

 

G와 D, B와 F처럼 같은 값을 가지는 알파벳끼리는 누구한테 더 높은 숫자를 주는지는 중요하지 않다.

 

각 알파벳이 가지는 숫자가 궁금한 것이 아니고 주어진 단어의 합의 최대값을 물어봤기 때문에

 

서열이 같은 알파벳 끼리의 누가 더 높은 수를 가지는지는 중요하지 않고 합이 중요하다.

 

 

코드

# 1339번

import sys

n = int(sys.stdin.readline())

alphabet_dict = {'A':0, 'B':0, 'C':0, 'D':0, 'E':0, 'F':0, 'G':0, 'H':0, 'I':0, 'J':0, 'K':0, 'L':0, 'M':0, 'N':0, 'O':0, 'P':0, 'Q':0, 'R':0, 'S':0, 'T':0, 'U':0, 'V':0, 'W':0, 'X':0, 'Y':0, 'Z':0}
alphabet_list = []
answer = 0
pocket = []

for _ in range(n):
    alphabet = input()
    pocket.append(alphabet)

for alphabet in pocket:
    for i in range(len(alphabet)):
        num = 10 ** (len(alphabet) - i - 1)
        alphabet_dict[alphabet[i]] += num

for value in alphabet_dict.values():
    if value > 0:
        alphabet_list.append(value)

sorted_list = sorted(alphabet_list, reverse=True)
for i in range(len(sorted_list)):
    answer += sorted_list[i] * (9 - i)

print(answer)

 

각 알파벳이 어떤 값을 가지는지 배정하는 방법을 고민하다가 딕셔너리를 이용하기로 했다.

 

어차피 입력값의 알파벳은 모두 대문자로만 주어지니 각 알파벳을 key로 두고 value를 0으로 설정한다.

 

입력값의 각 알파벳을 자리수에 따라 10의 제곱 수로 그 알파벳의 value값에 더해준다.

 

0번 인덱스부터 시작한다는 것을 감안해서 i 번째 인덱스라면 단어의 길이에서 i와 1만큼 빼준거를

 

10의 제곱수로 사용한다.

 

그렇게 딕셔너리의 value값에 다 더해주고나면 이 중에서 한번이라도 쓰인 알파벳은 value 값이

 

0보다 크기 때문에 0보다 큰 value값을 가지는 value들을 alphabet_list라는 리스트에 담는다.

 

앞서 말했듯이 어떤 알파벳이 무슨 값을 가지는지는 중요하지 않기 때문에

 

내림차순으로 정렬해주고 0번 인덱스부터 9부터 내림차순으로 값을 곱해준다.

 

마지막으로 다 더해준 값을 출력해주면 된다.

 

 

이 문제는 solved.ac 기준으로 골드티어에 해당하는 문제인데 골드 문제는 처음 풀어보았다.

 

평소라면 엄두도 안냈을 것 같은데 요즘 알고리즘 문제를 많이 풀면서 자신감도 얻고

 

그리디 알고리즘이 다른 알고리즘에 비해 난이도가 쉽다보니 도전했던 것 같다.

 

원래 파이썬을 하면서 딕셔너리에 자신감이 많이 없었는데 그냥 일반적인 배열로는 어떻게 풀어야

 

할지 감이 잘 오지않아서 딕셔너리를 사용하게 되었다.

 

딕셔너리를 활용하면 시간복잡도를 많이 줄일 수 있기 때문에 앞으로 사용할 환경이 된다면

 

적극적으로 활용할 수 있도록 하고 변수명을 좀 더 잘 짓는 연습을 해야할 것 같다.