[백준] 1339번 단위수학 -python 파이썬

문제

 

 

 

 

 

처음 이 문제를 보고 찾은 풀이법은 수의 최대길이가 8까지 이기때문에 모든 단어의 길이를 8로 맞추고

 

'*****AAA'

'*****AAA'

 

이렇게 적용된 단어들이 든 배열을 0번째 인덱스부터 확인하면서 가장 앞의 자리가 높은 숫자를 가지도록 해서 문제를 풀어주었다.

 

그러나 계속 해서 오답이 나왔다 ...

 

오답코드

n = int(input())
vocas = []
dic = {}
nums = [0,1,2,3,4,5,6,7,8,9]
for _ in range(n):
    tmp = input()
    l = len(tmp)
    vocas.append('*' * (8-l) +tmp)

vocas.sort(key = lambda x:len(x))
for i in range(8):
    for voca in vocas:
        if voca[i] != "*" and voca[i] not in dic:
            dic[voca[i]] = nums[-1]
            nums.pop()
            nums.sort()
ans = 0
for voca in vocas:
    tmp = ''
    for v in voca:
        if v != '*':
            tmp += str(dic[v])
    ans += int(tmp)


print(ans)

 

 

이유는 이렇게 문제를 풀 경우에 발생하는 예외가 있기때문이다.

 

 

예외)

ABB + BB + BB + BB + BB + BB + BB + BB + BB + BB

B : 11 * 10 = 110
A : 100

 

 

위와 같이 A가 가장 큰 자리수라고 해서 A에 9를 할당하게 될경우 B가 9가 되는 경우보다 전체 수의 합이 작아지게 된다.

 

 

이를 피하기 위해서는 먼저 10**자리수 를 각 자리수 마다 해주어서 해당 알파벳에 숫자가 배정되기 전의 전체 값을 구해준다. 그런 후 그 수가 큰 수부터 가장 큰 숫자를 할당 해주면 된다

 

 

예시 : GCF + ACDEB
A : 10000
C : 1010
G : 100
D : 100
E : 10
B : 1
F : 1

 

 

알파벳에 맞는 숫자가 배정되기 전의 값을 구하는 코드

dic = {}
for _ in range(n):
    tmp = input()
    l = len(tmp)-1
    for j in range(l,-1,-1):
        ch = tmp[l-j]
        if ch not in dic:
            dic[ch] = 10 ** j
        else:
            dic[ch] += 10**j

 

 

 

정답 코드

n = int(input())

dic = {}
for _ in range(n):
    tmp = input()
    l = len(tmp)-1
    for j in range(l,-1,-1):
        ch = tmp[l-j]
        if ch not in dic:
            dic[ch] = 10 ** j
        else:
            dic[ch] += 10**j
#숫자가 배정되기 전의 값을 기준으로 가장 큰것부터 앞에 오도록 정렬
dic = dict(sorted(dic.items(),key=lambda x:x[1], reverse=True))
#9부터 할당하기 위해 9부터 시작
num = 9
ans = 0

for alpha in dic:
    #해당 알파벳에 배정된 숫자를 곱해줌
    ans += dic[alpha] * num
    num -=1

print(ans)

 

 

 

 

 

단순히 큰 자리수가 큰 숫자로 배정이 되면 합이 가장 커질거라고 생각한게 오답의 원인이였다..

예외가 되는 부분에 대해서 더 신중하게 고민을 해보는게 필요하단걸 깨닫게 해준 문제였다.