1. 문제

88. Merge Sorted Array

Easy

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.

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

• 내림차순으로 정렬된 두 개의 정수 배열 nums1과 nums2가 주어지며, 각각 nums1과 nums2에 있는 요소의 수를 나타내는 두 개의 정수 m과 n이 주어집니다.
• nums1과 nums2를 감소하지 않는 순서로 정렬된 단일 배열로 병합합니다.
• 최종 정렬된 배열은 함수에 의해 반환되지 않고 nums1 배열 안에 저장되어야 합니다. 이를 위해 nums1의 길이는 m + n이며, 첫 번째 m 요소는 병합해야 하는 요소를 나타내고 마지막 n 요소는 0으로 설정되어 무시해야 합니다. nums2의 길이는 n입니다.

2. 접근 방법

두 개의 배열이 주어지면 배열이 크기를 먼저 확인했다. 케이스1은 친절하게 크기가 정해져 있어서 처음 주어진 배열에 두번째 배열을 추가로 넣어서 진행하면 되고, 케이스2,3은 크기가 존재하지 않는 배열이 있으므로 존재하지 않는 값은 신경쓰지 않고 두 배열을 병합하는 방법으로 접근하였다. 케이스1을 해결하고 나면 나머지 케이스2, 3은 저절로 문제가 풀어질거 같아서 케이스1 위주로 문제 풀이를 진행하였다.
내림차순으로 정렬해야 하니깐 List를 생성해서 병합한 배열을 생성된 List에 넣어서 해볼까 했지만 배열 자체도 정렬이 되어서 따로 생성하지 않고 진행하였다.

3. 의사 코드

반복문(0, 두번째 배열 크기, 1++) {
	배열1[주어진 배열1의 크기 -> 반복문을 돌때마다 1씩 증가] = 두번째 배열[0번째 순서부터 하나씩 가져오기]
}

병합한 배열 내림차순 정렬

4. 문제 풀이

import java.util.*;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
        for (int i = 0; i < n; i++) {
            nums1[m++] = nums2[i];
        }

        Arrays.sort(nums1);
    }
}

5. 개선 사항

sort() 메서드를 사용하게 되면 시간 복잡도가 늘어나기 때문에 속도측면에서는 좋지 않은거 같다. 투 포인터를 사용하는 방법을 이용하는게 속도 측면에서는 좋고 메서드에 의존하지 않고 논리적으로 푸는 방법이라 이렇게 접근하는 방법을 다시 한번 생각해 봐야겠다.

각각 m-1과 n-1로 초기화된 두 개의 포인터 i와 j로 시작할 수 있습니다.
또한 m+n-1로 초기화된 또 다른 포인터 k가 있는데, 이 포인터는 더 큰 요소를 배치할 nums1의 위치를 추적하는 데 사용됩니다.
그런 다음 배열 i와 j의 끝에서 반복을 시작하고 이 위치의 요소를 비교할 수 있습니다.
nums1에서 더 큰 요소를 k 위치에 배치하고 그에 따라 해당 포인터 i 또는 j를 감소시킵니다.
nums2의 모든 요소를 반복할 때까지 이 작업을 계속합니다.
nums1에 여전히 요소가 남아 있으면 이미 올바른 위치에 있으므로 아무 작업도 할 필요가 없습니다.

class 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--];
            }
        }
    }
}