백준(1339) - 단어수학 Python

백준(1339) - 단어수학

문제풀이 : 그리디 알고리즘, 파이썬

해결방법

알파벳 개수만큼 리스트를 생성한 후

큰수부터 해당 알파벳에 더해주면 된다.

최종적으로 리스트를 내림차순으로 정렬해 준 뒤 9부터 1씩 줄여가며 곱한 값을 더해주면 해결할 수 있다.

import sys
input = sys.stdin.readline

t = int(input())
words = []

for _ in range(t):
    words.append(input())

alphabet = [0 for i in range(26)]

for word in words:
    i = 0
    while word:
        now = word[-1]
        alphabet[ord(now) - ord('A')] += pow(10, i)
        i += 1
        word = word[:-1]

alphabet.sort(reverse=True)
ans = 0
for i in range(9, 0, -1):
    ans += i * alphabet[9 - i]
print(ans)

처음 풀었던 방법

복잡하게 풀긴 했지만 제출하면 틀렸다고 나오는데 왜 틀린방법인지는 아직 잘 모르겠다…

아시는 분이 있다면 댓글 달아주세요…ㅠ

문제 예시 GCF, ACDEB로 풀이방법을 설명하면

1. num 리스트에 [[F,B], [E],[G,D],[C],[D]] 처럼 정렬한다. (1의자리, 10의자리, 100의 자리..)

2. result_a 리스트에 [F,B,E,G,D,C,D] , result_num리스트에 [3,4,5,6,7,8,9] 를 정렬 시킨다.

3. 입력받았던 문자를 replace() 를 사용하여

replace(result_a[i], result_num[i])로 대체해준 후

결과값을 더한다.

import sys
input = sys.stdin.readline

n = int(input())
alpha = []
for i in range(65,91):
    alpha.append(chr(i))
words = []

for _ in range(n):
    a = input()
    words.append((len(a)-1, a[:len(a)-1]))

words.sort(reverse=True)
num = [[] for _ in range(words[0][0])]

cnt = 10
for word in words:
    size, w = word
    for x in w:
        num[size-1].append(x)
        cnt -= 1
        size -= 1
        
result_alpha = []
result_num = []
for nu in num:
    for n in nu:
        result_alpha.append(n)

result_alpha.reverse()
result_a = []
c = 9
for alp in result_alpha:
    for al in alp:
        if al in alpha:
            alpha.remove(al)
            result_a.append(al)
            result_num.append(str(c))
            c -= 1

result = 0
for word in words:
    size, wo = word
    for i in range(len(result_a)):
        wo = wo.replace(result_a[i], result_num[i])
    result += int(wo)

print(result)