🦊 36진수

1. 문제 링크

1036번: 36진수

2. 코드

Python3 31120KB 48ms

def to_36(number):
    global BASE
    
    a = number // 36
    b = number % 36
    
    if not a:
        return BASE[b]
    else:
        return to_36(a) + BASE[b]

# 36진수
BASE = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

N = int(input())

NUMBERS = []
for i in range(N):
    NUMBERS.append(input())

K = int(input())

# 가중치 초기화
WEIGHT = dict()
for i in range(36):
    WEIGHT[BASE[i]] = 0
    
for i in range(len(NUMBERS)):
    number = NUMBERS[i]
    
    # 각 자릿수 만큼 가중치 증가 (작은 수를 Z 로 바꿀수록 값은 더 커짐)
    length = len(number);
    for j in range(length):
        digit = number[j]
        WEIGHT[digit] += (35 - int(digit, 36)) * (36 ** (length - j - 1))
    
# 가중치가 높은 순으로 정렬 후 K 개 pick
sorted_weight = sorted(WEIGHT.items(), key= lambda x: -x[1])[:K]
picked = [item[0] for item in sorted_weight]

sum = 0
for i in range(N):
    number = NUMBERS[i]
    current = ""
    for ch in number:
        if ch in picked:
            current = current + "Z"
        else:
            current = current + ch
    sum += int(current, 36)
    
print(to_36(sum))

3. 해설

각 자릿수 별 가중치를 36의 제곱으로 더해줌 (파이썬의 biginteger 처리 덕분에 가능)

이 때 중요한 점은 작은 수를 Z 로 바꿨을 때 최댓값에 가까워지기 때문에

(35 - {해당 수의 값}) * (36^{자릿수}) 라는 수식으로 가중치를 구함

→ Z 의 가중치는 0이 되기 때문에 Z → Z로 바꾸는 연산은 36개를 모두 고를 때 이외에는 존재하지 않음

가중치가 가장 큰 것들을 K개 pick 해서 Z로 바꾼후 덧셈