LeetCode 88번: Merge Sorted Array(JAVA)
❔ 문제
오름차순으로 정렬된 두 배열 nums1과 nums2를 nums1 배열로 합쳐 하나의 오름차순된 배열을 구성하는 문제.
⏩ 예시
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.
❕ 문제풀이
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] arr = new int[m + n]; // 1.
int i = 0, j = 0, cur = 0;
while (i<m && j<n) { // 2.
if (nums1[i] <= nums2[j]){
arr[cur] = nums1[i];
i++;
}else{
arr[cur] = nums2[j];
j++;
}
cur++;
}
if (i < m) { // 3.
for (int k = cur; k < m+n; k++) {
arr[k] = nums1[i];
i++;
}
} else {
for (int k = cur; k < m+n; k++) {
arr[k] = nums2[j];
j++;
}
}
for (int k = 0; k < m+n; k++) {
nums1[k] = arr[k];
}
}
nums1, nums2 배열은 각각 정렬되어 있으므로 투포인터와 유사한 방식을 사용하였다.
- 새로 오름차순으로 정렬할 배열
arr을 선언 - 양쪽 배열을 첫 원소부터 순차적으로 비교하여 작은 값을 새 배열
arr에 순차적으로 삽입 - 한쪽의 배열의 원소는 새 배열에 전부 삽입되었으므로, 남은 한쪽의 삽입되지 않은 원소를 새 배열로 삽입
💯 고찰
처음 고안한 방법은 두 배열을 arr1로 합쳐 Arrays.sort()로 오름차순 정렬하는 방법이었는데, 문제 출제 의도에 적합하지 않은 것 같아 위 방식으로 풀이하였다.
Follow up: Can you come up with an algorithm that runs in O(m + n) time?
다만 타 사이트의 문제와 달리 return 값으로만 채점하지 않아 적잖히 당황하였다. 이에 맞춰 채점하는 공간의 값을 내가 새로 할당한 배열로 대체하여 풀이하려했는데 이는 LeetCode의 채점기준에 맞지 않았다.
결국 새롭게 선언한 배열의 값을 다시 채점하는 배열의 값에 대체시켜 코드가 상당히 지저분하게 되어버렸다. 분명 LeetCode에서 추구하는 기준은 이런 방식이 아닐 것이기에 Solution들을 참고하였다.
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
같은 투포인터를 사용하였는데 불구하고, nums1의 비어있는 뒷 공간을 활용하여 깔끔한 코드를 구성하여 매력적이었다.
