[코딩 테스트 연습(파이썬/Python)] 백준 1339번 _ 단어 수학

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

1339번: 단어 수학

[문제]

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

 

[입력]

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

[출력]

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

 

[아이디어]

1) 각 알파벳은 뒤에서부터 n번째 자리에 있는 경우 10^(n-1)을 곱한 값을 실제로 의미하게 된다.(10진법)

2) 각 알파벳에게 곱해줘야 하는 숫자를 dictionary에 모은 후에 그 크기 순서대로 9~n을 부여한다.

 

# 오답
n=int(input())
tmp = dict(); d=dict(); k=0
org = []
for _ in range(n):
    s=list(input())
    l = len(s)
    # (길이-1)의 최대 업데이트
    k = max(l-1,k)
    for i,x in enumerate(s):
        if x not in d:
            d[x] = -1
        org.append((x,l-1-i))
        tmp[l-1-i] = tmp.get(l-1-i,set())|{x}

def match(d,tmp,k):
    n = 9
    l = len(d)
    while n>=10-l and k>=0:
        if len(tmp[k])==1:
            d[tmp[k].pop()]=n
            n-=1
        else:
            tmp2 = [[0,x] for x in tmp[k] if d[x]==-1]
            c=k
            while c>=0:
                c = max(0,c-1)
                for j,(m,x) in enumerate(tmp2):
                    if x in tmp[c]:
                        tmp2[j] = [max(m,c),x]
                tmp2.sort(reverse = True)
                for i ,(_,x) in enumerate(tmp2):
                    d[x] = n-i
                c-=1
            n -= len(tmp2)
        k-=1
    return d
print(sum(map(lambda x: match(d,tmp,k)[x[0]]*10**x[1], org)))

테스트 케이스는 통과하지만,, 뭘 어떻게 생각한거지? 싶을 정도로 뻘짓을 했다. 앞에 나온 것부터 9를 부여하는 코드인데, 정확히 동작하지도 않는다.

 

10

ABB

BB * 9 

를 주는 경우 틀린다. 이 경우 A가 아니라 B에게 9를 부여해야 최댓값이 나온다.

 

n=int(input())
d=dict(); 
for _ in range(n):
    s=list(input())
    l = len(s)
    for i,x in enumerate(s):
        d[x] = d.get(x,0) + 10**(l-1-i)
dd = list(d.items())
dd.sort(key = lambda x: x[1], reverse = True)
answer = 0
for i,(_, x) in enumerate(dd):
    answer += x*(9-i)
print(answer)

정신차리고 보니 5분 컷 문제였다;;