[항해 99 코테 챌린지] 2231. 숫자들을 홀짝에 따라 교차한 숫자중 가장 큰 숫자 (Largest Number After Digit Swaps by Parity)

https://leetcode.com/problems/largest-number-after-digit-swaps-by-parity/description/

 

모르는 단어 및 표현

영어를 이상하게 이해해서 처음에 문제를 제대로 풀 수 없었다.

 

- digit

숫자, 자리 이렇게 사전에 나오지만 실제 의미는 0-9 까지의 아리비아 숫자라고 보면 된다.

즉 이런 상황에 쓸 수 있다. 

Password is made by 8 digits. (비밀번호는 8자리의 숫자로 구성되어 있습니다.)

우리가 일반적으로 이해할때 쓰이는 '자리' 하곤 다른게, 십의 자리, 백의 자리 ,일의 자리 를 의미할 때는 place를 쓴다 ^^;;

 

- parity

이것도 사전에 치면 바로 안나오는데, 패킷 검사할때 쓰이는 패리티 비트와 의미가 이어진다.

홀수, 짝수의 구분을 의미한다.

 

처음에 실수한 코드

이게 입력숫자가 10^9승인데, 짝-홀수에 따른 숫자 교환 작업을 재귀로 처리할라고 했다. 결국 시간초과.

from itertools import permutations
class Solution(object):
    def largestInteger(self, num):
        num = str(num)
        n_len = len(num)
        num_list = []
        def trans(num_,n):
            if(n >= n_len): return
            is_odd = int(num_[n]) % 2 == 1
            for j in range(0,n_len):
                is_odd2 = int(num_[j]) % 2 == 1
                if(is_odd != is_odd2): continue
                else:
                    temp = list(num_[0:])
                    temp[n], temp[j] = temp[j], temp[n]
                    num_ = ''.join(temp)
                    num_list.append(int(''.join(temp)))
                    trans(num_, n + 1)
                    temp[n], temp[j] = temp[j], temp[n]
                    num_ = ''.join(temp)
        trans(num,0)
        num_list.sort(reverse=True)
        return num_list[0]

수정한 코드

아무리 생각해도 10^9를 몸통박치기!로 다 밀어넣어보는건 아닌것 같아서, 방법을 고민한 결과 원래 숫자의 위치별로 짝 홀수 여부를 저장한 다음에, 짝이되는 수(짝-짝, 홀-홀) 중에서 큰걸 집어넣음 답이 되는걸 깨달았다.

 

from itertools import permutations
num = str(1234)
num_list = []
odd = sorted(list(filter(lambda x: int(x) % 2 == 1, num)), reverse=True)
even = sorted(list(filter(lambda x: int(x) % 2 == 0, num)), reverse=True)

# 원래 숫자 교차
result = []
for d in num:
    if int(d) % 2 == 0: # 원래 자리에 따라서
        result.append(even.pop(0))  # 가장 큰 숫자 사용
    else:
        result.append(odd.pop(0))  # 가장 큰 숫자 사용  
print(int(''.join(result)))

 

ㅠㅠ 입력범위가 넒으면 무식하게 처리하지 않고 다른 방법이 있을지 더 생각해 봐야겠다.