백준 1339번 단어 수학

< 백준 1339번 단어 수학 - 마포 코딩박>

사용한 알고리즘: 그리디..?


 알파벳으로 구성된 N개의 단어가 주어진다. 모든 단어에 쓰인 총 알파벳 종류는 10개 이하이다. 각 알파벳은 0~9 중 하나의 값을 갖을 수 있고, 서로 다른 알파벳은 같은 값을 갖을 수 없을 때, 단어들을 숫자로 변환해 더했을 때 최대값을 구하는 문제이다.

문제풀이는 다음과 같습니다.
(1) (코드: 12~19)
 단어가 주어지면, 각 알파벳이 몇개 있는지를 생각했습니다.
 예를들어 ABC가 주어지면, C는 1개, B는 10개, A는 100개 있는 것입니다.
 이에 따르면 ABC + BCD 인 경우는 A 100개, B 10+100개, C 1+10개, D 1개 있는 것이겠죠.

(2) (코드: 21~23)
 모든 단어을 각 알파벳별 개수로 저장한 후, 각 글자의 개수들을 sort해주었습니다.

(3) (코드: 25~29)
 개수가 많은 알파벳이 큰 Value를 갖으면 됩니다.
 예를 들어 모든 단어가 ABC , CA, DCB 로 주어져 모든 단어를 더하게되면, A 100+1개, B 10+1개, C 1+10+10 개, D 100개 가 더해지게 됩니다.
 따라서 A=9, D=8, C=7, B=6 으로 계산하면 덧셈의 최댓값을 구할 수 있습니다.