백준 1036번 36진수 풀이

오랜만에 푸는 백준문제~
https://www.acmicpc.net/problem/1036

언뜻 보면 쉬운 문제여서 시도해 보았다.

A부터 Z를 10부터 35로 변환하여 리스트에 담아준 뒤, summaiton이라는 함수를 통해 진수 계산으로 자릿수를 높여주는 함수를 먼저 만들었다.

def summation(num1, num2):
    result = []
    l1, l2 = len(num1), len(num2)
    if l1 < l2:
        num1, num2 = num2, num1
        l1, l2 = l2, l1
    
    up = 0 # 자리올림
    idx = 0
    while idx < l2:
        current = up + num1[idx] + num2[idx]
        up = current // 36
        result.append(current % 36)
        idx += 1
    
    while idx < l1:
        current = up + num1[idx]
        up = current // 36
        result.append(current % 36)
        idx += 1
    
    if up: result.append(up)
    # print(result, num1, num2)
    return result

def parse(s):
    num = []
    for c in s[::-1]:
        num.append(d[c])
    return num

def reverse(l):
    result = ''
    for e in l:
        result = r_d[e] + result
    return result

그 후, Z로 바꾸는 연산을 해주어야 하는데, 이에 대한 우선순위로 가장 높은 자릿수에 있는 것들을 골랐다.
비효율적이지만 enumerate해서 인덱스와 진수(0~35)를 추출해서 정렬한 뒤, 가장 높은 자릿수를 가져오는 방식을 택했다. 그러나 이 경우는 다음과 같은 경우에서 반례가 생긴다.

4
W0
Z0
Z0
ZX
1

https://www.acmicpc.net/board/view/69763 이곳을 참고했다!

다음과 같은 경우, 0을 Z로 대체하면 W를 Z로 대체한 것 보다 더 큰 기댓값을 얻을 수 있기 때문에 우선순위에 대한 계산식이 관건이었다.
이는 현재 선택한 숫자를 Z로 바꿀시에 대한 기댓값을 계산하고, 이를 기준으로 정렬하여 해결할 수 있는데, 여기까지 왔을 때 구현은 어렵지 않았다. 우선순위에 대해 생각해보는 것이 중요한 문제였다.

끄으윽