😊 백준 1339 : 단어 수학

1339: 단어 수학

Greedy 문제이다.
이번 껀 조금 난이도가 있었다. 풀고 보니, Gold 4 문제였다.

📌 Try 1

N = int(input())
words = dict()

for _ in range(N):
  word = list(input())
  digit = 1

  for w in reversed(word):
    words[w] = digit if w not in words else words[w] + digit
    digit *= 10

num, _sum = 9, 0
for w in sorted(words.items(), reverse=True, key=lambda x:x[1]):
  _sum += num * w[1]
  num -= 1

print(_sum)

어떻게 풀까 고민을 했고, 여러가지 방법이 떠올랐지만 선뜻 하나를 정하지 못했다.
한 블로그 글을 참고해서 방향을 정했고 코드는 모두 내가 작성했다.

나는 dict를 이용해서 풀고, dict를 정렬했다.
dict는 unordered 자료구조이기 때문에 풀긴 했지만,,, 개운치 않았다.

🎯 다른 분 코드

n = int(input()) 
word = [list(map(lambda x: ord(x)-65, input().rstrip())) for _ in range(n)] 
alpha = [0] * 26

for i in range(n): 
  j = 0   
  for w in word[i][::-1]: 
    alpha[w] += (10 ** j) 
    j += 1 

alpha.sort(reverse=True) 
ans, t = 0, 9 
for i in range(26): 
  if alpha[i] == 0:
    break
  ans += (t * alpha[i]) 
  t -= 1

print(ans)

double-list로 푸셨다.

🎁 Reference

• [백준알고리즘] 1339번: 단어 수학 -Python
  https://suri78.tistory.com/183