[백준 문제] 1339번 단어 수학 (파이썬)
[백준 문제] 1339번 단어 수학 (파이썬)
[백준 문제] 1339번 단어 수학를 풀어본다.
나의 생각의 흐름
- 첫번째 시도 :
- 순열로 다 넣어가면서 풀어보자.
- 알파벳이랑 숫자를 어떻게 매칭 시키지? 그래. 딕셔너리!
- 심지어 9부터 내림차순으로 넣으면 시간도 줄겠네?
- 코딩 후 오~ 잘되는데
- 9개 문자 들어갔더니 9! = 362880번 돌아가네?
- 백준에 채점
- 역시 시간 초과 후 급 노화
- 두번째 시도 :
- 아 순열 때려치고 넌센스문제라고 생각하자.
- {‘G’: 100, ‘C’: 1010, ‘F’: 1, ‘A’: 10000, ‘D’: 100, ‘E’: 10, ‘B’: 1} 이런식으로 딕셔너리 써서 만들고
- 이거를 내림차순으로 만들어서 9부터 넣으면 되겠다.
- 백준 채점
- 성공 급 회춘
깨달은점
- 일단 시간초과 뜰만한 코드는 짜지도 말자
- 변수이름을 좀 직관적으로 지어야 겠다. 다음날 다시 봤더니 뭐가 뭔지 하나도 모르겠어서 다시 짰다..
- 딕셔너리 공부좀 해야겠다
내 2번째 풀이 (성공)
# 단어 갯수 지정
word_n = int(input())
# 단어들 리스트 만들기
word_lst = []
for _ in range(word_n) :
word_lst.append(input())
# 문자들 마다에 곱해야할 수 딕셔너리화 시키기 {'G': 100, 'C': 1010, 'F': 1, 'A': 10000, 'D': 100, 'E': 10, 'B': 1}
alpha_digit_dic = {}
for each_lst in word_lst :
cnt = 0
for i in each_lst :
if i not in alpha_digit_dic :
alpha_digit_dic[i] = 10 ** (len(each_lst) - cnt - 1)
elif i in alpha_digit_dic :
alpha_digit_dic[i] += 10 ** (len(each_lst) - cnt - 1)
cnt += 1
# 딕셔너리 Key값을 내림차순으로 솔팅하고 9부터 차례대로 곱해주기
digit_lst = sorted(list(alpha_digit_dic.values()), reverse = True)
sum = 0
for i in range(len(digit_lst)) :
sum += digit_lst[i] * (9 - i)
ans = sum
print(ans)
내 첫번째 풀이 (시간 초과)
def prev_permutation(a):
i = len(a)-1
while i > 0 and a[i-1] <= a[i]:
i -= 1
if i <= 0:
return False
j = len(a)-1
while a[j] >= a[i-1]:
j -= 1
a[i-1],a[j] = a[j],a[i-1]
j = len(a)-1
while i < j:
a[i],a[j] = a[j],a[i]
i += 1
j -= 1
return True
N = int(input())
arr = []
lst = []
for _ in range(N) :
x = input()
arr.append(x)
## 중복 제거 리스트 만들기
for ele in arr :
lst += ele
lst = list(set(lst))
lst.sort()
## 딕셔너리 만들기
num = []
for i in range(len(lst)) :
num.append(9-i)
## 합계 계산기
def cal(a) :
sum = 0
for i in range(len(a)) :
sum += a[i]*10**(len(a)-i-1)
return sum
## 풀이
max_sum = 0
while True:
dic = dict(zip(lst, num))
all_sum = 0
for i in arr :
num_arr = []
for j in i :
num_arr.append(dic[j])
all_sum += cal(num_arr)
max_sum = max(all_sum, max_sum)
if not prev_permutation(num) :
break
print(max_sum)
