[Sort]99클럽 코테 스터디 29일차 TIL + 2327-largest-number-after-digit-swaps-by-parity

2327. Largest Number After Digit Swaps by Parity

Easy

---

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

 

Example 1:

Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

Example 2:

Input: num = 65875
Output: 87655
Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.
Swap the first digit 5 with the digit 7, this results in the number 87655.
Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.

 

Constraints:

• 1 <= num <= 109

---

 

<내 코드>

1. 처음방식 (문제를 잘못 이해함)

class Solution:
    def largestInteger(self, num: int) -> int:

        # 1. 짝수 홀수 분리
        str_num = str(num)
        even_num = [int(str_num[i]) for i in range(0,len(str_num), 2)] #짝수
        odd_num = [int(str_num[i]) for i in range(1,len(str_num), 2)] # 홀수

        odd_num.sort(reverse = True)
        even_num.sort(reverse = True)

        print(odd_num)
        print(even_num)

        output = []
        for i in range(len(str_num)):
            if i % 2 == 1: #홀수
                output.append(odd_num[i // 2])
            elif i % 2 == 0: #짝수
                output.append(even_num[i // 2])
        return int(''.join(list(map(str, output))))

1. 처음에는 홀수짝수 자릿수로 이해를 했음

그래서 해당방식으로 푸는 실수즐 저지름

그 이유는 패리티 라고 있어서 보통

내가 알기로 오류 검출을 위한 패리티 체크는 홀수자릿수 끼리 짝수자릿수끼리 에러 검출목적으로 하기 때문임

 

 

2. 풀었는 방식

class Solution:
    def largestInteger(self, num: int) -> int:

        str_num = str(num)
        # 1. 홀수 짝수 자릿수 찾기
        bigger = "even" if int(str_num[0]) % 2 == 0 else "odd"
        even_num_seat = [i for i in range(len(str_num)) if int(str_num[i]) % 2 == 0]  #짝수
        odd_num_seat = [i for i in range(len(str_num)) if int(str_num[i]) % 2 == 1] # 홀수

        # print(even_num_seat)
        # print(odd_num_seat)

        # 2. 자릿수의 수 중에 수 정렬하기
        even_num, odd_num = [], []
        for seat in even_num_seat:
            even_num.append(int(str_num[seat]))
        for seat in odd_num_seat:
            odd_num.append(int(str_num[seat]))
        even_num.sort()
        odd_num.sort()
        # print(even_num)
        # print(odd_num)

        # 3. 생성 후 처리하기
        output = [0 for i in range(len(str_num))]
        for v in even_num_seat:
            output[v] = even_num.pop()
        for v in odd_num_seat:
            output[v] = odd_num.pop()
        # print(output)
        return int(''.join(list(map(str, output))))

- 뒤늦게 파악 후 풀었음

1. 부족한 점

- pop() 은 O(n) 의 시간이 소요됨

 

- 복잡성 문제 : 짝수홀수 인덱스를 굳이 저장하고, 매핑하는 방식...

-> 굳이 이럴필요없이 곧바로 반복문에서 추출하면 괜찮은데...

 

 

<모범 사례>

- GPT version

class Solution:
    def largestInteger(self, num: int) -> int:
        str_num = str(num)
        even_digits = sorted([int(d) for d in str_num if int(d) % 2 == 0], reverse=True)
        odd_digits = sorted([int(d) for d in str_num if int(d) % 2 == 1], reverse=True)
        
        even_idx, odd_idx = 0, 0
        result = []
        
        for digit in str_num:
            if int(digit) % 2 == 0:
                result.append(str(even_digits[even_idx]))
                even_idx += 1
            else:
                result.append(str(odd_digits[odd_idx]))
                odd_idx += 1
                
        return int(''.join(result))

- 차이점

 

1. list comprehension + sorted

앞서 방식에서 sorted() 를 곧바로 생성하자마자 적용하는 방식으로 손쉽게 가능함

즉 list comprehension + sorted 로 쉽게 가능함

 

2. 짝수 홀수 자릿수 index 를 담을 필요없이 반복문과 조건문으로 바로 구별 가능함

 

- LeetCode

class Solution:
    def largestInteger(self, num: int):
        n = len(str(num))
        arr = [int(i) for i in str(num)]
        odd, even = [], []
        for i in arr:
            if i % 2 == 0:
                even.append(i)
            else:
                odd.append(i)
        odd.sort()
        even.sort()
        res = 0
        for i in range(n):
            if arr[i] % 2 == 0:
                res = res*10 + even.pop()
            else:
                res = res*10 + odd.pop()
        return res

- 효율적인 접근방식으로 접근이 가능함

 

- res * 10 이라는 연산방식으로 접근을 

 

 

<보충 학습>