[BOJ] 1339 단어 수학 - python

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

1339번: 단어 수학

 

풀이

처음에는 permutation써서 모든 순열 쌍을 다 구해서 풀이했는데 역시나 메모리 초과 최대 9개 쌍의 순서를 (9의9승) 다 비교하려하다니 아주 멍청스했다 이 문제는 greedy문제로 다 해보는 것이 아니라 자릿수의 중요도를 매겨서 최대 합을 구하는 문제였다. 10의 자릿수마다 중요도가 다르므로 그 중요도를 각 알파벳마다 저장해두어야 한다. 어차피 나중에 다 합치는 것이므로 한 알파벳이 해당 자릿수에 몇 번 나왔는지를 누적해서 저장

메모리 초과 코드

import sys
from itertools import permutations
#모든 단어에 최대 알파벳 개수 = 10개 (0~9)
#한 수의 최대 자리수 8자리

#모든 단어들을 분해해서 set에 넣어두고 가능한 모든 경우의 수 하기
#set(A,B,C,D,E) -> 9부터 알파벳 개수만큼
#뭐하나를 고정해놓기 (숫자를 고정 9,8,7,6,5)
#알파벳을 변경 (순열로 모든 조합 구하기)

def mInput():
    return sys.stdin.readline().rstrip()

N = int(mInput())
word = [mInput() for _ in range(N)]

def getAlphaNum(per):
    dict = {}
    for i,p in enumerate(per):
        dict[p]=9-i
    #print("DICT",dict)
    return dict

word_set = set()
for w in word:
    word_set.update(set(list(w)))
#print(word_set)

permut = list(permutations(word_set,len(word_set)))
#print("permut : " ,permut)

answer = 0
for per in permut:
    dict = getAlphaNum(per)
    #word 합 구하기
    sum = 0
    for w in word:
        alpha = list(w)
        alphaToNum = []
        for a in alpha:
            alphaToNum.append(str(dict[a]))
        num = int(''.join(alphaToNum))
        sum += num
    answer = max(answer,sum)

print(answer)

코드

import sys
# greedy -> 각 알파벳의 중요도를 기록하자
# 어차피 모든 알파벳의 합을 구하는 것이므로 각 알파벳이 존재하는 자릿수를 기록해놓는다면 최대를 구할 수 있음
def input():
    return sys.stdin.readline().rstrip()

N = int(input())
word = [input() for _ in range(N)]
alpha_dict = {}  # 알파벳별 자릿수에 몇 번 나타났는지를 기록할 딕셔너리

for w in word:
    for i, alpha in enumerate(w):
        if alpha in alpha_dict:
            alpha_dict[alpha] += pow(10, len(w) - i - 1)
        else:
            alpha_dict[alpha] = pow(10, len(w) - i - 1)

sorted_dict = list(alpha_dict.values())
sorted_dict.sort()
sorted_dict = list(reversed(sorted_dict))

sum = 0
number = 9
for sd in sorted_dict:
    sum += number * sd
    number -= 1
print(sum)

얻어가는 것

느낀점

"211111"

소요 시간 : 1h

• 메모리 초과, 시간 초과 생각해서 문제를 풀도록 하자
• 자릿수를 풀 때는 이렇게도 풀 수 있구나 를 깨달은 문제
• 잊고있었던 비트 연산을 생각나게 한 문제였다.