99클럽 코테 스터디 27일차 TIL

오늘의 학습 키워드

정렬

2231. Largest Number After Digit Swaps by Parity

Easy

Topics

Companies

Hint

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. 입력받은 숫자를 문자열로 변환하여 각 자릿수에 쉽게 접근할 수 있게한다.
2. 최종 결과값을 저장할 변수를 초기화 한다.
3. 길이가 2인 리스트를 생성한다.
   • maxHeap[0]은 짝수 숫자들을 위한 힙
   • maxHeap[1]은 홀수 숫자들을 위한 힙
4. 문자열의 각 숫자를 순회 하면서:
   • 문자를 정수로 변환한다.
   • digit % 2로 해당 숫자가 홀수인지 짝수인지 판단한다.
   • 해당하는 힙에 -digit를 push한다. (최대 힙을 구현하기 위해 음수로 저장)
5. 다시 원래 문자열을 순회 하면서:
   • i = int(c) & 1는 해당 자리의 숫자가 홀수인지 짝수인지 확인한다. (% 2와 동일한 효과)
   • ans * 10으로 현재 결과값을 한 자리 왼쪽으로 이동시킨다.
   • 해당하는 힙(짝수/홀수)에서 가장 큰 수를 꺼내서 더한다
   • 힙에 음수로 저장했기 때문에 빼기 연산을 사용한다.
6. 최종 결과를 반환한다.

   제출 코드 (python)

class Solution: 
    def largestInteger(self, num: int) -> int: 
        s = str(num) 
        ans = 0 
        maxHeap = [[] for _ in range(2)]

        for c in s: 
            digit = int(c) 
            heapq.heappush(maxHeap[digit % 2], -digit)

        for c in s: 
            i = int(c) & 1 
            ans = (ans * 10 - heapq.heappop(maxHeap[i]))

        return ans

오늘의 회고

• heapq를 이용한 정렬 방법을 응용했다