[Python/파이썬] 백준 1036번 36진수

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

 

코드

from collections import defaultdict

n = int(input())
nums = [input() for _ in range(n)]
k = int(input())

base36 = [str(x) for x in range(10)]+[chr(x) for x in range(65, 91)]


def decimal_to_base36(num):
    if num == 0:
        return "0"
    result = ""
    while num != 0:
        result = base36[num % 36]+result
        num //= 36
    return result


gap = defaultdict(int)
answer = 0
for i in range(n):
    answer += int(nums[i], 36)
    # nums[i]의 각 자리수와 "Z" 사이의 차이 저장
    for j in range(len(nums[i])):
        ch = nums[i][j]
        if ch != "Z":
            ch_value = int(ch, 36)

            gap[ch] += (35-ch_value)*(36**(len(nums[i])-1-j))

sorted_gap = sorted(gap.items(), key=lambda x: x[1], reverse=True)

for i in range(min(k, len(gap))):
    answer += sorted_gap[i][1]

print(decimal_to_base36(answer))

 

문제를 얼핏 보면 36개의 수 중 K개를 뽑는 모든 경우의 수를 다해보고 그 중 가장 큰 값을 구하면 되지 않나?싶을 수 있는데, 이렇게 하면 시간 초과가 발생할 것이다. 왜냐하면 k가 18이라고 하면 36C18인데 이 값은 9,075,135,300으로 약 90억 가지가 나온다. 그렇기 때문에 이렇게 하면 안된다.

 

그 대신 일단 주어진 수들의 합을 모두 구한 뒤, "Z"로 바꿨을 때 가장 효율이 좋은 경우만 찾아서 바꾸어 주어야 한다. 생각해보면 간단하다. 큰 지수의 자리에 많이 나오는 수들을 "Z"로 바꿔주면 된다.

 

이를 위해 gap이라는 딕셔너리에 각 글자를 "Z"로 바꿨을 때의 이득인 값을 누적해두고, 이 이득이 큰 순으로 정렬하여 상위 K개의 문자만 "Z"로 바꾼다. "Z"로 바꾼다는 것은 실제로 다시 계산할 필요는 없고, gap에 저장된 값을 더해주면 된다.