정렬된 두 개의 배열 A와 B가 있다고 가정해 봅시다. 이 두 배열을 병합하여 하나의 정렬된 배열 C를 만들어야 하며, 두 배열의 크기는 서로 달라도 됩니다.
예를 들어, A = [1,2,4,7]이고 B = [1,3,4,5,6,8]이라면, 병합된 배열 C는 [1,1,2,3,4,4,5,6,7,8]이 됩니다.
알고리즘 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- i := 0, j := 0으로 초기화하고, end := A의 길이 − 1로 설정합니다.
- end ≥ 0이면서 A[end]가 비어 있는(0인) 동안 end 값을 1씩 감소시킵니다. 이 과정은 배열 A에서 실제 데이터가 채워진 마지막 위치를 찾기 위함입니다.
- j가 B의 길이보다 작은 동안 아래 작업을 반복합니다.
- i > end이고 A[i]가 비어 있다면, A[i] := B[j]로 설정하고 j를 1 증가시킵니다.
- 그렇지 않고 A[i] > B[j]라면 shift(A, i)를 수행한 뒤, A[i] := B[j]로 설정하고 end와 j를 각각 1씩 증가시킵니다.
- i를 1 증가시킵니다.
shift 메서드의 동작 방식
shift 메서드는 요소를 삽입하기 위해 기존 요소들을 한 칸씩 뒤로 밀어내는 역할을 합니다.
- 배열 num_arr과 인덱스 i를 입력으로 받습니다.
- j := num_arr의 길이 − 1로 초기화합니다.
- num_arr[j]가 비어 있지 않은 위치를 찾을 때까지 j를 감소시킵니다.
- j ≥ i인 동안 num_arr[j + 1] = num_arr[j]를 수행하며 j를 1씩 감소시켜, i 이후의 모든 요소를 한 칸씩 뒤로 이동시킵니다.
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
class Solution(object): def merge(self, nums1, m, nums2, n): i = 0 j = 0 end = len(nums1)-1 while end>=0 and not nums1[end]: end-=1 while j<len(nums2) : if i>end and not nums1[i]: nums1[i] = nums2[j] j+=1 elif nums1[i]>nums2[j]: self.shift(nums1,i) nums1[i] = nums2[j] end+=1 j+=1 i+=1 return nums1 def shift(self,num,i): j = len(num)-1 while not num[j]: j-=1 while j>=i: num[j+1] = num[j] j-=1 ob = Solution() print(ob.merge([1,2,3,0,0,0],3,[2,5,6],3))
입력
[1,2,3,0,0,0] [2,5,6]
출력
[1, 2, 2, 3, 5, 6]
복잡도 분석 및 참고 사항
위 방식은 삽입 시마다 shift 연산으로 요소들을 뒤로 밀어내야 하므로, 최악의 경우 시간 복잡도는 O(m × n)입니다. 여기서 m과 n은 각각 두 배열의 길이입니다.
만약 배열 A 끝에 빈 공간(0)이 충분히 확보되어 있다면, 두 포인터를 배열의 뒤쪽부터 앞쪽으로 이동시키며 더 큰 값을 뒤에 채워 넣는 방식을 사용하면 O(m + n)의 시간 복잡도로 최적화할 수 있습니다. 이는 LeetCode의 'Merge Sorted Array' 문제에서 널리 알려진 표준 접근법입니다.