백준 - 1339번(그리디)

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

1339번: 단어 수학

 

import sys
from string import ascii_uppercase #대문자가 담겨있는 리스트

n = int(sys.stdin.readline())

arr = []
dic = {}
v_dic = {}
num = [0,1,2,3,4,5,6,7,8,9]

for _ in range(n):
    arr.append(sys.stdin.readline().rstrip())

for i in ascii_uppercase:
    dic[i] = -1 #할당값을 담아줄 대문자 딕셔너리
    v_dic[i] = 0 #우선순위를 저장할 대문자 딕셔너리

for i in arr:
    i = list(i)
    for j in range(len(i)):
        v_dic[i[j]] = v_dic[i[j]] + 10**(len(i)-(j))

v_dic = sorted(v_dic.items(), key = lambda x:x[1])


while num:
    x,y = v_dic.pop()
    dic[x] = num.pop()

ans = 0

for i in arr:
    i = list(i)
    for j in range(len(i)):
        i[j] = str(dic[i[j]])
    x = "".join(i)
    ans = ans + int(x)

print(ans)

그리디 알고리즘의 핵심은 정렬과 기준이라고 생각한다.

뭐를 기준으로 오름차순 or 내림차순 정렬을 할지 정해주고 나면 나머지는 구현 문제다.

최적해를 구하는 문제라서 당연한 얘기다.

해당 문제는 알파뱃을 각 숫자로 치환해서 합을 가장 크게 하는 문제다.

당연히 큰 숫자가 큰 값을 가질수록 유리할 것이다.

98765가 9x10^5 + 8x10^4 + 7x10^3... 이런 식으로 표현되는 걸 생각해보면 된다.
v_dic 딕셔너리에 해당 알파벳의 자릿수의 합의 값(우선순위 값)을 넣어준다.

예를 들어 ABCD 와 BEF 가 있으면 A는 10^3, B는 10^2 + 10^2, C = 10 이런 식으로 말이다.

우선순위 값이 같은 애들은 답을 출력할 때 더해지기 때문에 어떤 곳에 더 큰 수를 할당할지는 고려하지 않아도 된다.

가장 큰 값을 가지는 v_dic부터 큰 수를 할당해준다.

dic에는 해당 알파벳에 할당되는 실제 값을 반복문을 통해서 넣어주면 된다.
마지막에 입력받은 문자열을 정수로 치환해서 모두 더해주면 끝!