[그리디] 단어 수학

틀린 코드

첫번째 시도

n = int(input())

alpha = []
length = []
for _ in range(n):
  s = input()
  alpha.append(s)
  length.append(len(s))

alpha.sort(key=lambda x:len(x), reverse=True)

dict = {}
num = 9

def alpha_to_int(a, next):
  global num
  length = len(a)
    
  for i in a:

    if next <= len(alpha)-1 and length == len(alpha[next]):
    
      alpha_to_int(alpha[next], next+1)
    if i not in dict:
      dict[i] = num
      length -= 1
      num -= 1
    else:
      continue

#ABCD, DEF
#4자리 len(ABCD) + {지금 부여할 수 있는 수 중 가장 큰 수}, 3자리
length = len(alpha[0])
next = 1
result = 0
alpha_to_int(alpha[0], 1)

for string in alpha:
  length = len(string)-1
  for j in string:
    result += 10 ** length * dict[j]
    length -= 1

print(result)

 

단어 길이를 순차적으로 탐색하면서 길이가 가장 긴 문자열한테 큰 수부터 차례대로 할당해주고 그다음 길이간 긴 문자열한테 할당해주고... 이런식으로 했는데 이렇게 접근하니까 답도 안나오고, 너무 복잡하게 생각했나 싶어서 다른 코드를 찾고하였음.

 

다른 사람은 일단 입력 받은 알파벳을 모아놓고 알파벳 수 만큼 큰 수부터 permutation 라이브러리를 사용하여 순열을 통한 완전 탐색으로 사용된 알파펫에 모든 경우의 수를 대입해서 진행하였다. 아래 코드와 같다.

import sys
from itertools import permutations
N = int(sys.stdin.readline())
S = [0]*N
alpha = []
temp = {}
result = float('-inf')
for value in range(N):
    S[value] = sys.stdin.readline().strip()
    for a in S[value]:
        if a not in alpha:
            alpha.append(a) 
            
num = [i for i in range(9,(9-len(alpha)),-1)]
for m in permutations(num,len(alpha)): # 순열을 통한 완전탐색
    for i in range(len(num)):
        temp[alpha[i]] = m[i]
    sums = 0
    for j in S:
        letter = ''
        for k in j:
            letter += str(temp[k])
        sums += int(letter)
    result = max(result,sums)
print(result)

하지만 이 코드는 n = 10일 경우 순열을 통한 완전 탐색에서 10 * 10!이 되므로 2초안에 풀이가 풀가능하다

그래서 이 블로그에서 문제 접근 포인트를 읽으면서 해결 방법을 찾아보았다.

왜 문제를 못 풀었을까?

일단 나는 입력으로 주어진 알파벳을 쪼개서 수를 할당해준다는 아이디어를 떠올리지 못한게 문제풀이를 못한 가장 큰 이유고 생각한다.

"주어진 알파벳에서 다른 문자열과 비교하면서 자릿수가 더 큰 곳에 위치한 알파벳에 큰 수를 부여해야지" 라고 접근했었다. 문자열끼리 비교하는게 아니라 알파벳끼리 비교하면 되는 거였다. 어차피 모든 연산이 더하기니까 중복되는 알파벳을 모두 모아놓고, 알파벳 중에서 높은 자릿수를 차지한 알파벳에 높은 수를 부여하는 되는 것이였다.

 

정답 코드

n = int(input())
#먼저 각각 알바펫의 자릴수를 알아내야한다.
lst = [0 for _ in range(10)] #최대 10개의 알파벳
dict = {}
for _ in range(n):
  a = input()
  length = len(a)
  for i in range(length):
    if a[i] not in dict:
      dict[a[i]] = 10 ** (length-1)
    else:
      dict[a[i]] += 10 ** (length-1)
    length -= 1

dict = sorted(dict.items(), key=lambda x:x[1], reverse=True) #딕셔너러에서 리스트로 반환됨
result = 0

num = 9
for a, n in dict:
  result += n * num
  num -= 1
print(result)

---

ref

• https://edder773.tistory.com/97