[백준/1339/파이썬] 단어수학 - 그리디

---

소스코드

n = int(input())

digit = [0]*26

for _ in range(n):

    num = list(input().rstrip())

    for i in range(len(num)):

        digit[ord(num[i])-65] += 10 ** (len(num)-i-1)

digit.sort(reverse=True)

ans = 0

dig = 9

for i in digit:

    if not i:

        break

    ans += i*dig

    dig -= 1

print(ans)

---

알고리즘

이 문제는 그리디를 이용하여 풀 수 있는 문제이다.

찾아보니 딕셔너리를 이용한 풀이가 많았는데 입력이 대문자 알파벳이란 특성을 가지고 푸는 풀이가 있어서 힌트를 얻어 풀 수 있었다.

ord('A')는 A의 아스키 코드 65를 나타내어서 알파벳마다 몇번 포함이 되었는지를 저장하는 배열에 추가하였다.

digit[ord(num[i])-65] += 10 ** (len(num)-i-1)

이 부분인데 

A : digit[0] += 10**4

B : digit[1] += 10**3

이런 느낌이다.

리스트를 정렬하면

[1000,101,10]이런 형태로 정렬이 되고최대 숫자부터 9,8,7,... 곱해서 더해주면 된다.