[맛있는물회] [파이썬] <백준 알고리즘> 1339번 "단어 수학"

문제 조건

---

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

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

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

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

 

Input

---

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

 

Output

---

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

 

생각한 아이디어

---

더워서 그런지 머리가 잘 안돌아간다.. ㅎㅎ

 

 

맨첨에 permutation으로 싹 다 돌려서 max 값을 계산했다.

근데 알파벳의 개수가 10개일때는 몇개야,,, 10^10 인가 10!인가...

어쨌든 시간초과 발생!!

 

살짝 그리디 적인 방법으로 풀어야한다.

확실히 골드4넘어오니깐 문제들이 넘 어렵다...

자리수를 기준으로 가중치를 부여한다.

만약 중복되는 수가 있더라도 상관없다.

왜냐면 어짜피 더해주는 값이기 때문에 저게되든 이게되든 더한 값은 동일하다!

 

라고 생각을 했으나,,,,,

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

내가 코드를 잘 못 짰었다...

10의 제곱수 값을 그냥 대입하는 것이 아니라 각 값에 더해주어야 한다.

 

만약 입력 값이

 

ABC

ACB

CAA

일때

 

A: 100 + 100 + 10 + 1

B: 10 + 1

C: 1 + 10 + 100

이렇게 해주어야 올바른 가중치 값이 나온다.

소스코드

import sys
import operator
input=sys.stdin.readline

if __name__ == "__main__":
   n=int(input())
   arr=[list(input().rstrip()) for _ in range(n)]
   alp=[]
   for a in arr:
      for b in a:
         alp.append(b)
   alp=list(set(alp))
   alp={i:0 for i in alp}
   res={i:0 for i in alp}
   for a in arr:
      j=1
      for i in range(len(a)-1,-1,-1):
         alp[a[i]]+=j
         j*=10
   alp=sorted(alp.items(), key=operator.itemgetter(1), reverse=True)

   idx=9
   for a in alp:
      res[a[0]]=idx
      idx-=1

   ans=0
   for a in arr:
      tmp=''
      for b in a:
         tmp +=str(res[b])
      ans+=int(tmp)
   
   print(ans)

 

*파이썬 문법 정리