[1주차] 88. Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array/

 

처음에는 단순히 sort 라이브러리를 이용하여 O(nlogn) 시간에 풀었다.

for (i in nums2.indices) {
	nums1[m + i] = nums2[i]
}
nums1.sort()

m, n <= 200 이므로 물론 해결완료 였으나 문제 밑에

 

Can you come up with an algorithm that runs in O(m + n) time?

 

O(m + n) 시간에 해결해 보라고 하길래 다시 도전하였다.

 

문제 이름에 걸맞게 Merge sort 의 중간 병합 과정 알고리즘을 사용하기로 하였다.

하지만 이전에 Merge sort 를 구현하였을 때에는 버퍼를 두고 포인터 두 개를 사용하여 병합 후, 원본 배열에 복사하는 방법을 사용하였었다.

 

merge 과정

i가 가리키는 값과 j가 가리키는 값을 비교하여 작은 순 부터 원본배열로 옮긴 후, 임시배열의 원소를 원본으로 복사하는 방법이다.

하지만 nums1에는 n+m 만큼의 공간이 이미 할당되어있기 때문에 추가 버퍼를 사용 할 필요가 없다. 때문에 조금 다른 방식을 사용하기로 하였다.

 

위와 알고리즘과 동일하게 투포인터를 사용하지만, 배열 마지막부터 정렬을 한다. 첫 번째부터 정렬을 시도하면 원소를 뒤로 밀거나 추가 버퍼가 필요해 지기 때문이다.

var p1 = m - 1
var p2 = n - 1
var p3 = nums1.lastIndex

while (p1 >= 0 && p2 >= 0) {
    if (nums1[p1] > nums2[p2]) {
        nums1[p3--] = nums1[p1--]
    } else {
        nums1[p3--] = nums2[p2--]
    }
}

if (p1 >= 0) {
    while (p1 >= 0) nums1[p3--] = nums1[p1--]
}

if (p2 >= 0) {
    while (p2 >= 0) nums1[p3--] = nums2[p2--]
}

p1이 가리키는 값과 p2가 가리키는 값을 비교하여 큰 값을 p3에 저장하고 포인터를 왼쪽으로 이동시킨다.

p1과 p2가 둘 중 하나라도 0보다 작아지면 루프를 끝낸다. 그 이후 p1과 p2 중 남은 이동을 마무리 하면 된다.

위 방법으로 O(m + n) 시간에 Solve.

n,m 값 범위가 작기 때문에 sort() 를 사용하는 방법과 시간이 다르진 않다.

 

---

문제 해결 후 다른사람의 풀이를 보던 중 재밌는 코드를 발견했다.

var i = m - 1
var j = n - 1
var k = m + n -1
while (j >= 0) {
    nums1[k--] = if (i < 0 || nums1[i] < nums2[j]) nums2[j--]
             else nums1[i--]
}

처음에 이 코드를 봤을 땐 잘 이해가 가지 않았다.

j만 끝까지 밀고 끝내면 i가 남을 땐 어떻게 되는 거지?

하지만 애초에 i는 무조건 -1까지 이동시킬 필요가 없다. nums1과 nums2가 오름차순으로 정렬되어 있는 상황에서 j가 먼저 -1에 도달했다는 것은 nums2 배열의 모든 원소가 현재 i가 가리키는 원소보다 크다는 의미이고, 이는 i 뒤에 전부 삽입된 상태이다.

 

따라서 남은 i 포인터는 0까지 이동할 필요가 없다.