[백준 파이썬] 1339 단어 수학

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

1339번: 단어 수학

 

문제



알파벳에 적절한 숫자를 부여하여 합이 최대가 되게 하는 문제이다.

---

풀이

 

먼저 최대값을 구하는 방법을 생각해야한다.

예제의 GCF + ACDEB의 경우

783 + 98654 로 계산할 수 있다.

이는 가장 높은 자리의 알파벳에는 높은 숫자를 부여하고 낮은 자리의 알파벳은 낮은 숫자를 부여하는 방법으로 해결할 수 있다.

 

먼저 단어를 입력받고 해당 단어를 배열로 저장한다.

그러면

['G', 'C', 'F']

['A', 'C', 'D', 'E', 'B']

의 형태로 저장될 수 있다.

또한 알파벳에 숫자를 할당하기 위해 dictionary를 사용한다.

S = [list(input()) for _ in range(N)]
words = {}

 

이후 각 배열을 순회하며 알파벳에 가중치를 부여한다.

G, C, F의 경우 자리수를 고려하여 G에 10^2, C에 10^1, F에 1을 더하여 dictionary에 넣어준다.

이렇게하면 dictionary자료형인 word에

word[G] = 100

word[C] = 10

word[F] = 1

의 숫자가 부여된다.

 

또한 이미 부여되어있는 알파벳일 경우 해당 배열의 자리수의 따라 합해준다.

for s in S:
    x = len(s) - 1
    for i in s:
        if i in words:
            words[i] += 10**x
        else:
            words[i] = 10**x
        x -= 1

 

이렇게 부여한 가중치를 역순으로 정렬하여 변수에 할당한다.

그러면 다음과 같은 배열이 나오게된다.

[10000, 1010, 100, 100, 10, 1, 1]

sortedWord = sorted(words.values(), reverse=True)

 

마지막으로 sortedWord를 순회하며 9부터 곱해주면 정답이 된다.

num = 9
for k in sortedWord:
    result += k * num
    num -= 1

 

 

 

코드

from collections import deque

N = int(input())

S = [list(input()) for _ in range(N)]
words = {}

for s in S:
    x = len(s) - 1
    for i in s:
        if i in words:
            words[i] += 10**x
        else:
            words[i] = 10**x
        x -= 1
        
sortedWord = sorted(words.values(), reverse=True)
result = 0

num = 9
for k in sortedWord:
    result += k * num
    num -= 1
print(result)