•
문제 설명
◦
정렬되지 않은 nums1 과 nums2 와 각각의 길이 m , n 이 주어진다.
◦
이때 nums1 의 길이는 m + n 이며, nums1 에 nums1 과 nums2 가 합쳐지고 정렬된 배열로 설정되도록 한다.
•
풀이 방법
◦
결국, 병합된 배열도 오름차순으로 설정해야한다.
◦
그래서, 양쪽 배열 중 큰 수를 먼저 가져와 맨 뒤를 채워주며 순회하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
merge_array_cursor = len(nums1) - 1
nums1_cursor = m - 1
nums2_cursor = n - 1
# 오름차순이기 때문에, 두 배열의 가장 마지막 요소부터 거꾸로 비교한다.
# 병합된 배열 맨 뒤부터 overwrite 한다.
while nums1_cursor >= 0 and nums2_cursor >= 0:
if nums1[nums1_cursor] > nums2[nums2_cursor]:
nums1[merge_array_cursor] = nums1[nums1_cursor]
nums1_cursor -= 1
else:
nums1[merge_array_cursor] = nums2[nums2_cursor]
nums2_cursor -= 1
merge_array_cursor -= 1
# 만약 nums2가 모두 사용되지 않았다면, 마저 설정한다.
while nums2_cursor >= 0:
nums1[merge_array_cursor] = nums2[nums2_cursor]
nums2_cursor -= 1
merge_array_cursor -= 1
Python
복사