[알고리즘] 백준 1339 단어수학 / python

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

1339번: 단어 수학

 

✔ 풀이과정

원래는 순열을 이용하는것같은데.. 파이썬은 딕셔너리를 사용해야지 시간초과가 안나나보다😢

딕셔너리에 각 숫자의 자리값을 저장해놓고 내림차순으로 정렬한다음, 제일 큰 수인 9부터 곱해준다.

이 예제로 설명하자면

dictionary = { G:100, C:1010, F:1, A:10000, D:100, E:10, B:1 } 이렇게 자리값을 10의 n승으로 저장한다.

sort_list = [('A', 10000), ('C', 1010), ('G', 100), ('D', 100), ('E', 10), ('F', 1), ('B', 1)] value값을 기준으로 내림차순 정렬한다.

(람다식을 사용하면 튜플를 가진 리스트로 변함)

튜플의 두번째 원소들을 9부터 곱해주면 최댓값이 나올것이다.

 

N = int(input())
word = []
for _ in range(N):
    word.append(list(input()))

dic = {}
#문자의 자릿수에 따라 10의 n승 더해주기
#ex. G:100, C:10, F:1
for i in range(len(word)):
    for j in range(len(word[i])):
        if word[i][j] not in dic:
            dic[word[i][j]] = pow(10, len(word[i])-j-1)
        else:
            dic[word[i][j]] += pow(10, len(word[i])-j-1)

#value의 값을 기준으로 정렬
sort_list = sorted(dic.items(), key=lambda x: x[1], reverse=True)
result, num = 0, 9
#정렬된 값이 앞에 있을수록 자릿수가 크다는 거니까 9부터 곱해주면서 결과에 더해주기
for i in range(len(sort_list)):
    result += num * sort_list[i][1]
    num -= 1

print(result)