LeetCode [2231]: Largest Number After Digit Swaps by Parity

📌 LeetCode [2231]: Largest Number After Digit Swaps by Parity

🔗 문제 링크

---

문제 설명 📄

주어진 정수 num의 각 자릿수를 교환하여 다음 규칙에 따라 가장 큰 수를 만드세요:

• 짝수끼리는 교환 가능하며, 홀수끼리는 교환 가능하지만 짝수와 홀수는 교환할 수 없습니다.

---

문제 접근 방식 📋

1. 짝수와 홀수 판단 함수:
   • 각 숫자를 짝수와 홀수로 분류하기 위해 mod 2 연산을 사용합니다.
2. 배열 변환:
   • 주어진 숫자 num을 문자열로 변환하고, 각 자릿수를 리스트로 변환하여 작업합니다.
3. 정렬:
   • 현재 인덱스와 이후의 숫자를 비교하며 같은 성질(짝수/홀수)을 가지는 숫자 중 가장 큰 값을 찾습니다.
4. 최종 결과 반환:
   • 리스트를 다시 문자열로 합친 후 정수로 변환하여 반환합니다.

---

Solution 💻

class Solution:
    def largestInteger(self, num: int) -> int:
        nums = [int(i) for i in str(num)]

        def jud(num):
            return True if num % 2 == 0 else False

        for i in range(len(nums)):
            flag = jud(nums[i])
            maxValue = nums[i]
            for j in range(i + 1, len(nums)):
                if flag == jud(nums[j]):
                    if maxValue < nums[j]:
                        maxValue = nums[j]
                        nums[i], nums[j] = nums[j], nums[i]

        return int("".join(map(str, nums)))

시간 복잡도 ⏲️

• 내부 루프 탐색: 각 자릿수를 탐색하며 이후의 숫자를 비교하므로, 최악의 경우 (O(n²))의 시간 복잡도를 가집니다.
  • n은 자릿수의 개수입니다.

공간 복잡도 🗄️

• 리스트 변환: 숫자를 리스트로 변환하는 데 (O(n)) 공간이 사용됩니다.
• 최종 결과 저장: 리스트를 문자열로 합친 후 정수로 변환하므로 (O(n)) 공간이 추가적으로 필요합니다.
• 총 공간 복잡도: (O(n)).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def largestInteger(self, num: int) -> int:
        nums = [int(i) for i in str(num)]
        odds = sorted([x for x in nums if x % 2 == 1], reverse=True)
        evens = sorted([x for x in nums if x % 2 == 0], reverse=True)

        for i in range(len(nums)):
            if nums[i] % 2 == 0:
                nums[i] = evens.pop(0)
            else:
                nums[i] = odds.pop(0)

        return int("".join(map(str, nums)))

리팩토링 후 시간 복잡도 ⏲️

• 정렬: 짝수와 홀수 리스트를 각각 정렬하므로 (O(n log n)).
• 최종 대입: 리스트를 한 번 순회하며 값 대입 (O(n)).
• 총 시간 복잡도: (O(n log n)).

리팩토링 후 공간 복잡도 🗄️

• 정렬된 리스트 저장: 짝수와 홀수 리스트에 (O(n)) 공간이 사용됩니다.
• 총 공간 복잡도: (O(n)).

---