You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Explanation: The arrays we are merging are [1] and []. The result of the merge is [1].
Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Explanation: The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
Constraints:
nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109Follow up: Can you come up with an algorithm that runs in O(m + n) time?
리트코드에서의 첫번째 문제에요.
2개의 non-decreasing order 배열을 input으로 받으면, 2개의 배열의 모든 데이터를 합친 non-decreasing order 배열 하나를 output하면 되는 간단한 문제에요.
너무 쉬운 문제이긴 하지만..
여튼, 저는 보자마자 정형화된 유형인 두 포인터를 떠올렸고, 바로 해답을 생각해냈습니다.
각각의 배열에서 index 0에서 시작하는 각 cursorA, cursorB를 정의한 후에 cursorA를 standard로 삼고, cursorA와 cursorB를 비교해서 cursorA의 알맞은 자리에 cursorB의 데이터를 삽입하며 cursorA와 cursorB를 점차 증가시키며 끝까지 이동시키는 것이죠.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def merge(self, nums1, m, nums2, n):
idxm = 0
idxn = 0
while idxm < m and idxn < n:
if nums1[idxm] >= nums2[idxn]:
nums1.insert(idxm, nums2[idxn])
idxn = idxn + 1
idxm = idxm + 1
m = m + 1
else:
idxm = idxm + 1
while len(nums1) != m:
nums1.pop()
nums1.extend(nums2[idxn:n])
첫 코드는 그런대로 좀… 마음에 들지는 않아요. python을 쓰면서 c/c++ 느낌의 스타일이 짙게 묻어나오고 있어요. (취업 전 백준에서 몇 백개 가량의 알고리즘 문제를 풀 때 모두 C++로 풀어대서 그런지 내 코딩스타일은 C++에 맞추어져 있는 듯 해요)
![[Pasted image 20240427195242.png]] code try 1 - submission result
간단하게 제출하고 결과를 확인했는데,, 실행시간 부분에서는 조금 놀랐어요. 물론 다양한 굇수들이 python의 기상천외한 방법들로 실행시간을 단축시켜놨을 거라 예상은 했지만, while로 짠 간단한 코드가 상위 37% 시간에 밖에 들지 못했다는 것에.. 조금 놀랐어요. (그런데 어찌보면 당연한 것 같긴 해요. pop(), insert() 등 불필요한 함수를 사용했으니. 이 코드 작성 바로 다음에 insert 와 pop 함수를 제외한 [[#code try 2|코드]]를 바로 작성했어요.)
그리고 Solutions에 다른 사람들이 공유해놓은 Solution은 대체 어떤 것들이 있는지 바로 첫번째 글을 봤는데.. 좀 어이가 없었네요..
![[Pasted image 20240427200246.png]] first post in Solutions
이…이게 뭐지…!? 정렬 알고리즘..을 그대로 쓴.,.. 간단한 해답..
아, 물론 여러가지 복합적인 문제를 풀 때에는 C++ STL 사용이 필수적이고, 그 안에서 sort 함수도 당연히 사용하며 시간 복잡도도 계산하지만,, 요렇게 간단한 문제에 적용할 거라고는 상상도 못했어요. 한 방 얻어맞은 느낌이네요.
![[Pasted image 20240427200615.png]]Submission result of first post in Solutions
시간도 꽤 준수하게 나오는 것 같고…
하긴.. 사이즈 200 정도의 아주 작고 간단한 문제에 시간은 들쑥날쑥할 것 같긴 해요. 실제로 몇 번 더 돌리면 돌릴 수록 제 해답과 sort() 함수 사용한 해답 시간이 계속 엎치락 뒤치락 하네요.
뭐… 아무튼… 사담이 길었어요. 요약해보면,,
로 생각해야겠어요.
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def merge(self, nums1, m, nums2, n):
idx1 = m - 1
idx2 = n - 1
cursor = m + n - 1
while cursor >= 0:
if idx1 < 0 or (idx2 >= 0 and nums1[idx1] <= nums2[idx2]) :
nums1[cursor] = nums2[idx2]
idx2 = idx2 - 1
else:
nums1[cursor] = nums1[idx1]
idx1 = idx1 - 1
cursor = cursor - 1
![[Pasted image 20240427201732.png]]code try 2 - submission result
시간복잡도를 좀 더 줄여보고자 python list의 pop과 insert 함수를 사용하지 않고 해봤어요. 오히려 시간이 늘어나는 기현상이 발생했지만.. 아까 얻은 [[#교훈]]에 따라서.. runtime은 신경쓰지 않기로 했어요.