[BOJ] 1132 합 (Python)

from collections import defaultdict
N = int(input())
d = defaultdict(int)
for i in range (0,12):
    d[chr(i + 65)] = 0 #각각의 인덱스 저장

cant_zero = []
for i in range (0,N):
    s = input() #입력되는 문자
    n = len(s)
    for j in range (0,n):
        if j == 0:
            cant_zero.append(s[j])
        d[s[j]] += 10 ** (n - 1 - j)

spell = []
for i in range (0,12):
    if d[chr(i + 65)] != 0:
        spell.append([chr(i+65) , d[chr(i + 65)]])
spell.sort(reverse = True, key = lambda x: x[1])
can_zero = []
revised = []

for i in range (0,len(spell)):
    if spell[i][0] in cant_zero:
        revised.append(spell[i])
    else:
        can_zero.append(spell[i])

if len(revised) <= 9:
    for i in range (0,len(can_zero)):
        revised.append(can_zero[i])
    if len(revised) <= 9:
        for j in range (0,9):
            revised.append([0,0])
            
revised = revised[0:9]
revised.sort(reverse= True, key = lambda x : x[1])

ans = 0
for i in range (0,9):
    ans += revised[i][1] * (9-i)
print(ans)

 

골드 3 문제였는데, 꽤 그래도 재밌게 풀은 느낌이 든다.

 

도중 몇가지 작업이 필요가 없을 수도 있었는데, 일단은 굉장히 빠르게 해결할 수 있었으니 ... 일단은 만족하는 것으로.

 

 

가장 중요한 아이디어 중 하나는, 0이 될 수 없는 문자들을 미리 분류해두고 우선순위에 둘 필요가 있는 것이다.

 

이 알고리즘에서는 알파뱃들을 총 2번에 걸쳐서 필터링을 하였다.

 

첫번째로, spell 리스트에서의 for문인데, 여기서 0이 될 수 없는 것들을 우선적으로 revised라는 리스트에 넣어줄 필요성이 있었다.

 

두번째로, if len(revised)에서, 길이를 강제로 9로 만들어주는 방법을 취하였다. 

 

꽤 재밌었던 문제 같았다.