https://leetcode.com/problems/create-maximum-number/description
핵심 아이디어
- 숫자 붙여서 최댓값 만들기 + 순서 유지 -> Greedy
- 정렬 + 순서 유지 -> Decreasing Monotonic Stack
- 리스트의 사전 순 비교는 Python의
max(list1, list2)
를 이용할 수 있다
(결과 길이) < (l1 + l2 길이)
이면 -> l1, l2 모든 길이 조합 경우의 수 구하기- 어떤 값을 안 쓰면 결과 달라지기 때문
- 숫자 붙이기 - Greedy결과가 최댓값이 되는 건 모든 값을 사용하는 조건에서만 성립한다
설명
이 문제는 아래처럼 나누어서 풀어야 한다
- 두 리스트를 조합해서 가장 큰 결과를 만든다
- Greedy하게 큰 값 선택
- 같은 값이면 뒤의 값을 순차적으로 비교
- 사전 순 비교와 같음
- => python
max(list1, list2)
사용 가능
- 모든 자릿수 조합에 대해서 가장 큰 두 개의 리스트를 만든다
- 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가 두 리스트 길이의 합보다 작으면 값을 제외할 수 있어서 결과가 달라진다.
- 순서대로 Greedy로 고른
- nums1 =
- 경우의 수 나누지 않고 순서대로 Greedy만 하면 뒤에 나오는 값이 더 클 수 있다. 따라서 값을
코드 (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
'Problem Solving' 카테고리의 다른 글
[LeetCode] 42. Trapping Rain Water - 스택 풀이 (Python) (0) | 2024.03.01 |
---|---|
[LeetCode] 5. Longest Palindromic Substring (JS) (0) | 2022.09.03 |
[LeetCode] 49. Group Anagrams (JS) (0) | 2022.09.03 |
[LeetCode] 819. Most Common Word (JS) (0) | 2022.09.03 |
[LeetCode] 937. Reorder Data in Log Files (JS) (0) | 2022.09.03 |