문제
내림차순으로 정렬된 두 개의 정수 배열 nums1과 nums2가 주어지며, 각각 nums1과 nums2에 있는 요소의 수를 나타내는 두 개의 정수 m과 n이 주어집니다.
nums1과 nums2를 감소하지 않는 순서로 정렬된 단일 배열로 병합합니다.
최종 정렬된 배열은 함수에 의해 반환되지 않고 nums1 배열 안에 저장되어야 합니다. 이를 위해 nums1의 길이는 m + n이며, 첫 번째 m 요소는 병합해야 하는 요소를 나타내고 마지막 n 요소는 0으로 설정되어 무시해야 합니다. nums2의 길이는 n입니다.
풀이
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int index1 = m - 1, index2 = n - 1, mergeIndex = m + n - 1;
while (index1 >= 0 && index2 >= 0) {
if (nums1[index1] > nums2[index2]) {
nums1[mergeIndex--] = nums1[index1--];
continue;
}
nums1[mergeIndex--] = nums2[index2--];
}
while (index2 >= 0) {
nums1[mergeIndex--] = nums2[index2--];
}
}
}고민 요소
이 문제에서 새로운 ArrayList나 int 배열을 생성하게 되면, 기존의 nums1이 아닌 새로운 배열을 생성하게 된다.
문제에서 주어진 nums1 배열을 그대로 이용해야 되는 게 포인트이다. 그냥 0을 제외하고 합친후 sort를 해서는 풀수가 없다.
그림으로는 위와 같은 방식으로 동작하게 된다.
