난이도

Gold 1

문제

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

해설

꽤 난도있는 구현 문제였다. 그러나 복잡한 알고리즘이 사용되거나 하지는 않았다. 구현하고자 하는 바는 풀어서 쓰면 간단한데, 우선 입력받은 36진수를 각 레벨별로 끊어서 저장한다. 그리고 등장하는 모든 36진수에 대해, 해당 숫자를 ‘Z’로 변환할 시 기대 가능한 증가치를 숫자와 함께 리스트로 저장한다. 마지막으로 그 리스트를 증가치 기준으로 정렬하고, k만큼 리스트에서 가져와 더한다. 그리고 그 10진수를 36진수 숫자로 변환한 후 출력한다.

36진수로 변환하는 과정에서 carry를 엄밀하게 설정하지 못해 몇번 틀렸다.

제출 코드

import sys
n = int(sys.stdin.readline().rstrip())
orgLst = [] #입력 그대로 저장될 리스트
for i in range(n):
    tmp = sys.stdin.readline().rstrip()
    orgLst.append(tmp)
  
m = 0 # maxLevel. 1부터 시작함 ex) 1234 = level 4

for j in orgLst: # 순회하며 maxLevel을 구함
  if(len(j) > m):
    m = len(j)

lst = [[] for i in range(m)] #왼쪽부터 레벨 0부터 저장될 리스트
for i in orgLst: # 순회하며 레벨 정렬
  tmpMax = len(i)
  for j in range(len(i)):
    lst[tmpMax-j-1].append(i[j])

k = int(sys.stdin.readline().rstrip())

# 각 레벨을 순회하며 후보군으로 가능한 알파벳을 뽑음. 가장 뒷레벨부터 뽑으며 이미 있는 알파벳의 경우 통과
nom = [] # 뽑힌 알파벳이 저장될 리스트. [알파벳, 레벨]을 담고 있음
for i in reversed(range(m)): # 만약 m = 4 라면 3, 2, 1, 0 ...
  for j in lst[i]: # 이제 j는 알파벳, i는 그 알파벳의 레벨을 담음
    # nom에 알파벳이 중복되지 않도록 처리
    flg = 0
    for u in nom:
      if(j == u[0]):
        flg = 1
    if(flg == 1):
      continue
    else:
      nom.append([j, i])

# nom을 순회하며 그 알파벳을 Z로 변환했을 때 증가하는 정도를 저장 ex) nom = [[123, 'A'], ...]
calc = []
for i in nom:
  alpha = i[0] # 현재 순회중인 알파벳
  lev = i[1] # 알파벳이 위치했던 최대 레벨
  realNum = ord(alpha) - 48 # 알파벳의 실제 10진수 넘버
  if realNum > 10:
    realNum = realNum - 7
  
  # 이제 0부터 lev까지 순회하며 그 알파벳을 Z로 변환할 때 값을 계산한다.
  tmp = 0 # 합을 저장할 변수
  for j in range(lev+1): # 0, 1, ... , lev
    for u in lst[j]:
      if(u == alpha):
        tmp += (35-realNum) * (36**(j)) # 이 알파벳이 Z로 변하면 증가하는 양
  calc.append([tmp, alpha])

calc.sort(reverse=True) # calc를 큰 것부터 정렬
realMax = 0 # k만큼 Z로 바꿨을 때 증가하는 10진수 수
for i in range(min(k, len(calc))): # k만큼, 혹은 후보의 수만큼(전부 Z로 변환할 때) 순회
  realMax = realMax + calc[i][0]

orgMax = 0 # 입력된 값의 합
for i in orgLst:
  orgMax += int(i, 36) # 36진수 변환을 지원하므로 변환해 orgMax에 증가

numLst = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' # 36진수 리스트
realMax = realMax + orgMax # 출력값의 10진수 형태
if (realMax == 0):
  print(0, end='')
  exit()

cvtLst = [] # 출력할 값을 저장할 리스트
# realMax를 36진수로 변환
tmp = realMax
while(tmp >= 36):
  cvtLst.append(numLst[tmp % 36])
  tmp = tmp // 36
  
cvtLst.append(numLst[tmp % 36])
for i in reversed(cvtLst):
  print(i, end='')