[LeetCode] 321. Create Maximum Number (Python)

https://leetcode.com/problems/create-maximum-number/description

핵심 아이디어

• 숫자 붙여서 최댓값 만들기 + 순서 유지 -> Greedy
  • 정렬 + 순서 유지 -> Decreasing Monotonic Stack
  • 리스트의 사전 순 비교는 Python의 max(list1, list2)를 이용할 수 있다
• (결과 길이) < (l1 + l2 길이)이면 -> l1, l2 모든 길이 조합 경우의 수 구하기
  • 어떤 값을 안 쓰면 결과 달라지기 때문
  • 숫자 붙이기 - Greedy결과가 최댓값이 되는 건 모든 값을 사용하는 조건에서만 성립한다

 

설명

이 문제는 아래처럼 나누어서 풀어야 한다

1. 두 리스트를 조합해서 가장 큰 결과를 만든다
   • Greedy하게 큰 값 선택
   • 같은 값이면 뒤의 값을 순차적으로 비교
     • 사전 순 비교와 같음
     • => python max(list1, list2) 사용 가능
2. 모든 자릿수 조합에 대해서 가장 큰 두 개의 리스트를 만든다
   • k = 4라면, 두 리스트의 자릿수 경우의 수는 (0, 4), (1, 3), (2, 2), (3, 1), (4, 0) 이다
   • 모든 자릿수 조합에 대해서 구해야 하는 이유는 결과 길이가 nums1 + nums2 길이보다 작을 수 있기 때문이다
     • 경우의 수 나누지 않고 순서대로 Greedy만 하면 뒤에 나오는 값이 더 클 수 있다. 따라서 값을 k - i 만큼 제외하는 경우를 포함해야 한다
     • ex)
       • nums1 = [3, 9]
       • nums2 = [8, 9]
       • k = 3
         • 순서대로 Greedy로 고른 [8, 9, 3] 보다 [9, 8, 9](nums1의 길이=1 인 경우)가 더 크다
         • 모든 값을 다 쓰는 경우라면 Greedy하게 [8, 9, 3, 9]가 맞다. 그러나 k가 두 리스트 길이의 합보다 작으면 값을 제외할 수 있어서 결과가 달라진다.

 

코드 (Python)

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        def find_max_sequence(nums, length):
            """
            nums에서 길이가 length이고 원본 리스트의 순서를 유지하는 가장 큰 숫자 리스트를 반환합니다
            Decreasing Monotonic Stack을 이용합니다
            """
            # 버린 수 개수
            # 입력한 자릿수를 충족하는 만큼만 버릴 수 있습니다
            drop_counter = len(nums) - length
            out = []

            for num in nums:
                # Decreasing Monotonic Stack 깨지면서
                # 자릿수 만족할 수 있을 때
                while drop_counter and out and out[-1] < num:
                    out.pop()
                    drop_counter -= 1
                out.append(num)

            return out[0:length]

        def merge(list1, list2):
            """
             두 개의 리스트를 합치고 순서를 유지하여 가장 큰 값을 만듭니다
            """
            merged = [
                max(list1, list2)  # 앞 자리수 큰 것부터 뽑고, 같으면 뒷 자리수 정럴 큰 것부터
                .pop(0) for _ in list1 + list2
            ]
            return merged

        # (0, n) ~ (n, 0) 가능한 모든 자릿수 조합 중에서 큰 것 선택
        return max(merge(find_max_sequence(nums1, i), find_max_sequence(nums2, k - i))
                   for i in range(0, k + 1)
                   if i <= len(nums1) and k - i <= len(nums2)
                   )

 

참고 자료

https://www.youtube.com/watch?v=ZHexy3JW2JA&t=104s

https://algo.monster/liteproblems/321