[파이썬] 백준 1036 : 36진수 (골드1)

[파이썬] 백준 1036 : 36진수 (골드1)

 

1036번: 36진수

---

문제

---

풀이

0. 방향성 생각

진법 변환 문제. 그리디 태그가 있는데 내가 푼 풀이도 그렇고 그리디 치고 뭐 생각할게 없어서 문자열이 더 맞는 듯 하다.

 

단일 입력이 들어왔을 때 어떤 식으로 다룰 것인가.

• 변환할 가능한 수 문자열에 나타난 종류보다 같거나 많은 경우
• 변환할 가능한 수의 개수가 문자열에 나타난 종류보다 적은 경우

다중 입력이 들어왔을 때 어떤 식으로 다룰 것인가.

• 변환이 불가능한 경우
• 전부 변환이 가능한 경우
• 일부만 변환이 가능한 경우

이 경우를 나눠서 풀었다.

 

1. 입력 받기

import sys
input = sys.stdin.readline

n = int(input())
arr = []
num36 = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'

# 진법 변환기
table_36_10 = dict(zip(num36,range(36)))
table_10_36 = dict(zip(range(36),num36))

# 사용된 문자열 used에 넣기
used = set()
for i in range(n):
    temp = input()
    arr.append(temp)
    for j in temp :
        used.add(j)
used = list(used)

change = int(input())

 

2. 계산 함수 작성

def calculator(num_list):
    ans = [0]*50
    for number in num_list :
        temp = list(map(lambda x:table_36_10[x],number))
        ans = list(map(lambda x,y:x+y,temp,ans))
    ans = ans + [0]*3 # 오버플로우 방지

    for idx,val in enumerate(ans):
        if idx < len(ans)-2 :
            p,q = divmod(val,36)
            ans[idx] = q
            ans[idx+1] += p
            
    s = ''
    for i in ans:
        s += table_10_36[i]
    s = s.rstrip('0')
    
    if not s : return 0
    else: return s[::-1]

['GOOD','LUCK','AND','HAVE','FUN'] 이런 다중 입력이 들어왔을 때 계산하는 함수이다.

['DOOG0000000000000000000000000000000000000000000000',

'KCUL0000000000000000000000000000000000000000000000', 'DNA00000000000000000000000000000000000000000000000', 'EVAH0000000000000000000000000000000000000000000000', 'NUF00000000000000000000000000000000000000000000000']

이런식으로 50자리 36진법 숫자를 만들어서 각 자리수 별로 더해준다.

처음 0으로 초기화된 ans에다가 순서대로 자리수별로 변환해서 입력을 더해준다

변환하고 난 후에 오버플로우 방지를 위해서 [0]을 더 붙여준다.

 

각 자리수별로 36으로 나누어주어서 나머지는 그 자리에, 몫은 다음 자리에 더해준다.

s에 10진수를 다시 36진수로 변환하여 넣어준다. 오른쪽의 자리는 더미 MSB이므로 제거해준다. 이후 뒤집어주기.

값이 0인경우 strip을 진행하면 0이 되므로 경우를 나누어서 리턴해준다.

 

2. 단일 입력이 들어오는 경우

if len(arr) == 1:
    temp,s = [],arr[0]
    
    for i in s:
        if i not in temp and i != 'Z':
            temp.append(i)
            
    if len(temp) <= change :
        print('Z'*len(s))
    else :
        for i in temp[:change]:
            s = s.replace(i,'Z')
        print(s)

단일 입력인 경우 'Z'를 제외한 문자가 CHANGE보다 같거나 많으면 모두 'Z'로 치환이 가능하다.

아닌 경우 temp에 MSB부터 들어가므로 먼저 등장한 순서대로 Z로 바꿔서 출력한다.

 

3. 다중 입력이 들어오는 경우 :  변환 불가, 전부 변환하는 경우

else :
    cal = []
    if not change: # 못바꾸는 경우
        for num in arr:
            leng = len(num)
            s = '0'*(50-leng)+ num
            cal.append(s[::-1])
            
    elif change > len(used): # 전부 바꾸는 경우
        for num in arr:
            leng = len(num)
            s = '0'*(50-leng)+ 'Z'*leng
            cal.append(s[::-1])

못 바꾸는 경우는 입력을 50자리로 만들고 뒤집어서 계산기에 넣는다.

전부 바꾸는 경우는 전부 Z로 변환하고 50자리로 만든 후 뒤집어서 계산기에 넣는다.

4. 다중 입력이 들어오는 경우 :  일부만 변환이 가능한 경우

    else :
        gain_list = [] # (바꾼 문자,증가량) 추가
    
        for key in used: # 등장한 문자 하나씩 치환
            arr_changed = []
            for num in arr:
                num_changed = num.replace(key,'Z')
                arr_changed.append(num_changed)

            temp_cal = [] # 50자리로 변환 후
            for num in arr_changed:
                leng = len(num)
                s = '0'*(50-leng)+ num
                temp_cal.append(s[::-1])
            if key != 'Z' : # z는 변환할 필요 X
                gain_list.append((key,calculator(temp_cal))) # 계산기에 넣고 돌리기
        gain_list.sort(key= lambda x:(len(x[1]),x[1])) # 상위 CHANGE개 정렬

        gain_key = set()
        for key,val in gain_list[-change:]:
            gain_key.add(key)
        
        arr_changed = []
        for num in arr:
            s = ''
            for i in num :
                if i in gain_key : s += 'Z'
                else : s += i
            arr_changed.append(s)
            
        for num in arr_changed:
            leng = len(num)
            s = '0'*(50-leng)+ num
            cal.append(s[::-1])

    answer = calculator(cal)
    print(answer)

gain list에 임의의 문자 하나를 Z로 변환했을 때 리스트에 (변환한 문자,결과값)을 저장한다.

여기서 증가량이 큰 상위 change개를 뽑는다.

입력에 대해서 그 문자열들을 전부 치환해서 계산기에 넣고 돌려주면 된다.

---

전체코드

import sys
input = sys.stdin.readline

n = int(input())
arr = []
num36 = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'

table_36_10 = dict(zip(num36,range(36)))
table_10_36 = dict(zip(range(36),num36))

used = set()
for i in range(n):
    temp = input().rstrip()
    arr.append(temp)
    for j in temp :
        used.add(j)
used = list(used)

change = int(input())

def calculator(num_list):
    ans = [0]*50
    for number in num_list :
        temp = list(map(lambda x:table_36_10[x],number))
        ans = list(map(lambda x,y:x+y,temp,ans))
    ans = ans + [0]*3

    for idx,val in enumerate(ans):
        if idx < len(ans)-2 :
            p,q = divmod(val,36)
            ans[idx] = q
            ans[idx+1] += p
    s = ''
    for i in ans:
        s += table_10_36[i]
    s = s.rstrip('0')
    
    if not s : return 0
    else: return s[::-1]

if len(arr) == 1:
    temp,s = [],arr[0]
    
    for i in s:
        if i not in temp and i != 'Z':
            temp.append(i)
            
    if len(temp) <= change :
        print('Z'*len(s))
    else :
        for i in temp[:change]:
            s = s.replace(i,'Z')
        print(s)
else :
    cal = []
    if not change:
        for num in arr:
            leng = len(num)
            s = '0'*(50-leng)+ num
            cal.append(s[::-1])
            
    elif change > len(used):
        for num in arr:
            leng = len(num)
            s = '0'*(50-leng)+ 'Z'*leng
            cal.append(s[::-1])
        
    else :
        gain_list = []
    
        for key in used:
            arr_changed = []
            for num in arr:
                num_changed = num.replace(key,'Z')
                arr_changed.append(num_changed)

            temp_cal = []
            for num in arr_changed:
                leng = len(num)
                s = '0'*(50-leng)+ num
                temp_cal.append(s[::-1])
            if key != 'Z' :
                gain_list.append((key,calculator(temp_cal)))
        gain_list.sort(key= lambda x:(len(x[1]),x[1]))

        gain_key = set()
        for key,val in gain_list[-change:]:
            gain_key.add(key)
        
        arr_changed = []
        for num in arr:
            s = ''
            for i in num :
                if i in gain_key : s += 'Z'
                else : s += i
            arr_changed.append(s)
            
        for num in arr_changed:
            leng = len(num)
            s = '0'*(50-leng)+ num
            cal.append(s[::-1])

    answer = calculator(cal)
    print(answer)

코멘트

복잡하게 풀긴 했는데 골1치고 어려운 문제는 아니다. 좀 더럽게 풀긴 했지만

아무리 봐도 틀린데가 없어서 계속 제출했는데 에러뜨길래 rstrip 썼는데 맞아버림..

 

0000같은 경우는 0으로 들어가야 될거같은데 ZZZZ로 나오는데 정답이다. 이 부분은 추가가 수정이 필요할듯?