[백준 1339] 단어 수학- python (solved.ac - 골드 4)

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

1339번: 단어 수학

풀이

문제를 보았을 때 알 수 있는 힌트

문제를 보고 조합 형식으로 풀어야하나 했지만 큰값만 잘 찾아놓으면 풀수 있는 그리디 문제였다.

자리수가 큰를 찾아서 리스트로 정리해놓는다.

예를 들어 GCF + ACDEB 라고 하면

ACDEB

     GCF

여기서 두 값을 더하려 위치에 맞게 값을 넣으면 

A = 10000

C = 01010

D = 00100

G = 00100

E = 00010

B = 00001

F = 00001

이렇게 적힌 리스트를 내림차순으로 정렬후 9부터 1까지 내려가며 곱하면 값이 나온다.

A = 10000 * 9 = 90000
C = 1010 * 8 = 8080
D = 100 * 7 = 700
G = 100 * 6 = 600
E = 10 * 5 = 50
B = 1 * 4 = 4
F = 1 * 3 = 3

이렇게 하여 더하면 99437이 나온다.

import sys

input = sys.stdin.readline

n = int(input())
n_list = [list(input().strip()) for _ in range(n)]
n_dic ={}
result = 0

for i in range(n):
    for j in range(len(n_list[i])):
        if n_list[i][j] in n_dic:
            n_dic[n_list[i][j]] += 10 ** (len(n_list[i])-j-1)
        else:
            n_dic[n_list[i][j]] = 10 ** (len(n_list[i])-j-1)

n_dic_list =[]
for val in n_dic.values():
    n_dic_list.append(val)

n_dic_list.sort(reverse=True)
count = 9
for i in n_dic_list:
    result+= count*i
    count-=1
print(result)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/python/baekjoon1339.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리