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

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

1339번: 단어 수학

문제유형 : 그리디

 

문제풀이 :

 

< 처음 생각한 풀이 - 예외케이스가 발생함 > 

• 가장 자릿수가 큰 숫자의 길이만큼 모든 숫자의 길이를 늘려준다. (rjust이용해서 오른쪽 정렬후 앞자리에 의미없는 문자 삽입 )
• 자릿수가 큰 숫자부터 차례대로 순서를 부여한다. 9부터
• 이렇게 풀면 ,AB 와 BB와 같은 경우를 해결하지못함, 해결하려면 경우의수를 다 따져가며 결국 완탐느낌이 되버림

< 정답풀이 >

• 각 문자에 자릿수만큼 count하고 그 count된 자릿수가 큰 숫자부터 그리디하게 가장 큰수를 부여함 
• ex) AB, BB인 경우 A는 10, B는 12가 되기때문에 B에게 A보다 큰 숫자를 부여하게 된다.

 

정답코드 :

import sys
from collections import *
input = sys.stdin.readline

n = int(input())
word_list = []
word_dic = defaultdict(int)
word_num = dict()

word_set = set()

max_len = 0

for _ in range(n):
    word = input().strip()
    word_list.append(word)
    for idx, c in enumerate(word[::-1]):
        word_dic[c] += int(10**idx)

#print(word_dic)
word_dic = sorted(word_dic.items(), key=lambda x:x[1], reverse=True)

begin = 9
cnt = 0
for item in word_dic:
    word_num[item[0]] = begin-cnt
    cnt += 1

result = 0

for word in word_list:
    num = ''
    for c in word:
        num += str(word_num[c])
    result += int(num)

print(result)