[백준] 1339번 - 단어 수학 (파이썬)

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

# 단어 수학
from collections import deque
N = int(input())
arr = []
for _ in range(N):
    arr.append(deque(list(input().strip())))
alpha = {}

for i in range(N):
    j = 0
    while True:
        if len(arr[i]) == 0:
            break
        if arr[i][j] in alpha:
            alpha[arr[i].popleft()] += 10**(len(arr[i]))
        else:
            alpha[arr[i].popleft()] = 10**(len(arr[i])-1)

list = []
for i in alpha.values():
    list.append(i)
list.sort(reverse=True)

result = 0
num = 9
for i in list:
    result += i*num
    num -= 1

print(result)

 

그리디

딕셔너리와 deque를 이용했다.

1. 인접리스트로 값을 전부 받아온다

2. arr을 0부터 돌면서 모든 j의 값을 참고한다

    - arr[i][j]가 alpha딕셔너리에 이미 있으면, 해당 값에 10의 현재길이제곱을 곱해준다 (popleft()를 해주어서 길이가 -1된 상태로)

    - arr[i][j]가 alpha딕셔너리에 없으면, 새로운 딕셔너리를 추가해준다

      (popleft()가 값이 대입연산자의 값이 계산되고 실행이 되는 거 같다 그래서 -1을 해주었다.)

3. 해당 딕셔너리의 값들을 전부 list리스트에 넣어주고 정렬을 한다(reverse)

4. list배열에 num을 곱한 값을 result에 더해준다 (num -= 1)

5. result 출력

 

까다로웠다. 그리디 구현 인것은 알겠는데 어떻게 해야 할까 하다가 모든 배열의 자릿수를 미리 구해서 그 값을 알고

추후에 곱해주는 방식으로 접근을 해서 풀었다.