[백준/1036] 36진수 (Python)

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

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:26:22

 

---

 

문제 설명

 

 

36진법의 숫자는 0부터 9까지의 수와 알파벳 A에서 Z로 나타낸다. A부터 Z까지 알파벳은 10부터 35에 차례대로 대응한다.

36진법의 수 N개가 주어진다. 36진법 숫자(0-9, A-Z) 중에서 K개의 숫자를 고른다. 그러고 나서 N개의 수 모두에서 나타난 그 숫자를 Z로 바꾼다. 그 이후에 N개의 수를 모두 더한다.

이때 가능한 합의 최댓값을 구하는 프로그램을 작성하시오. 합의 최댓값도 36진수로 출력한다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 수의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 수가 주어진다. N은 최대 50이고, 수의 길이도 최대 50이다. 마지막 줄에 K가 주어진다. K는 36보다 작거나 같은 자연수 또는 0이다.

 

출력

 

첫째 줄에 문제의 정답을 출력한다.

 

입력 예시

 

5
GOOD
LUCK
AND
HAVE
FUN
7

 

출력 예시

 

31YUB

 

 

---

 

풀이

 

그리디 문제. 각 자리수를 'Z'로 바꾸었을 때의 기댓값을 먼저 전부 계산해 볼 수 있다. 여기서 기댓값은 (36('Z') - 현재 숫자) * 36^(현재 자릿수)가 될 것이다. 즉 모든 문자열에 대해 기댓값 총합을 구할 수 있다면, 그 기댓값 총합이 높은 순대로 전부 Z로 바꾸어버리면 된다. 또한 이 때 최종 값은 (원래값 + 기댓값 총합 중 상위 K값의 합)이 된다.

 

두 가지 엣지 케이스, 즉 K = 0 인 케이스(원래 값 그대로 출력) 및 0만이 입력으로 들어오는 케이스 (0을 그대로 출력) 정도를 고려해 주자.

 

풀이 코드

from collections import defaultdict

N = int(input())
num_dict = defaultdict(int)
sum_val = 0
for i in range(N) :
  num = input().strip()
  length = len(num)
  for i in range(length) :
    if num[i].isdigit() :
      exp_val = (35 - int(num[i])) * 36 ** (length - i - 1)
      sum_val += int(num[i]) * 36 ** (length - i - 1)
    else :
      exp_val = (25 - ord(num[i]) + ord('A')) * (36 ** (length - i - 1))
      sum_val += (ord(num[i]) - ord('A') + 10) * 36 ** (length - i - 1)
    num_dict[num[i]] += exp_val
K = int(input())
num_list = sorted(num_dict.values(), reverse = True)
for i in range(min(K, len(num_list))) :
  sum_val += num_list[i]
  
answer = ''
while sum_val :
  num = sum_val % 36
  if num >= 10 :
    num = chr(num + 55)
  answer = str(num) + answer
  sum_val //= 36

print(answer if answer else '0')

풀이 완료!