문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

정렬되지 않은 두개의 정수 배열 nums1과 num2, nums1과 nums2의 요소의 개수를 나타내는 두 정수 m과 n이 주어진다.

nums1과 num2를 하나의 배열로 병합하고, 오름차순으로 정렬해라.

최종적으로 정렬된 배열은 함수에서 반환하지 않는 대신에 배열 nums1에 저장되어야한다. 이를 위해 nums1의 길이는 m + n이며, 처음 m개의 요소는 병합해야 할 실제 요소들이며, 마지막 n개의 요소는 0이 되어 무시한다. nums2의 길이는 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: 병합하려는 배열은 [1, 2, 3]과 [2, 5, 6]이다.
병합결과는 [1, 2, 2, 3, 5, 6]이다. 굵게 처리된 요소는 nums1에서 온 것이다.

#2
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: 병합하려는 배열은 [1]과 []이다.
병합결과는 [1]이다.

#3
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: 병합하려는 배열은 []과 [1]이다.
병합결과는 [1]이다.
주의할 점은 m = 0이라서 nums1에는 요소가 없다. 0은 단지 병합결과가 nums1에 들어갈 수 있도록 공간을 확보하기 위함이다.

Constraints

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200

Solved

하나의 포인터를 두고 두 배열을 순회하며 해당 요소에 값을 넣게 문제를 풀었다.

변수 idx, i, j를 선언하고 각각 m + n - 1, m - 1, n - 1을 할당한다.

int idx = m + n - 1;
int i = m - 1;
int j = n - 1;

배열 nums1의 크기가 m + n이며 빈 공간은 0으로 채워져 있어서 뒤에서부터 순회한다. 순회하면서 nums1[i]가 nums2[j]보다 크면 nums1[idx--]에 nums1[i--]를 할당하고, 그렇지 않다면 nums1[idx--] = nums2[j--]를 할당한다.

while(i >= 0 && j >= 0) {
  if(nums1[i] > nums2[j]) {
    nums1[idx--] = nums1[i--];
  } else {
    nums1[idx--] = nums2[j--];
  }
}

이때 nums2에 남은 수가 있어서 j가 0보다 크거나 같을 때까지 순회한다.

while(j >= 0) {
  nums1[idx--] = nums2[j--];
}

All Code

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int idx = m + n - 1;
        int i = m - 1;
        int j = n - 1;

        while(i >= 0 && j >= 0){
            if(nums1[i] > nums2[j]){
                nums1[idx--] = nums1[i--];
            }else{
                nums1[idx--] = nums2[j--];
            }
        }

        while(j >= 0){
            nums1[idx--] = nums2[j--];
        }
    }
}