[LeetCode/Top Interview 150] [Array / String] 88. Merge Sorted Array

문제 링크: https://leetcode.com/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
비내림차순인 두 integer 배열 nums1, nums2과 각 배열의 요소의 숫자를 나타내는 integer m과 n이 주어진다.
(* 비내림차순: 오름차순과 유사하지만, 인접한 요소의 값이 동일할 수 있음.)
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
nums1과 nums2를 하나의 비내림차순 배열로 합치시오.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
최종 결과물인 배열은 함수의 리턴값으로 리턴되지 않고, nums1배열로 저장되어야 합니다.
그러기 위해서는 nums1의 길이가 m + n이 되어야 하며, 처음에는 m개의 요소들은 병합되기 전의 요소들을 나타내며, 마지막 n 개의 요소들은 0으로 표시하고 무시해야 합니다. nums2는 n의 길이를 가집니다.

Constraints:
제약조건:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

전략:

nums1의 0으로 비어있는 부분에 nums2를 저장한 후, Arrays.sort로 정렬한다.
처음 m개의 요소는 nums1의 실제 데이터이므로 m+1번째 요소부터 덮어쓴다.

코드 구현:

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

실행결과:
Time: 1 ms (38.52%), Space: 40.8 MB (98.39%) - LeetHub
https://github.com/1-vL/LeetCode/tree/main/0088-merge-sorted-array

개선 방안:

Arrays.sort 보다 빠른 Collections.sort를 사용한 다음 다시 배열로 변환?
-> 오히려 비효율적이고 느려짐
처음 방식보다 더 빠른 방식이 생각나지 않음

Discuss 탭의 타인 코드:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int j = 0, i = m; j < n; j++) {
        // 거의 동일하지만 더 깔끔하고 좁은 범위의 for 문
            nums1[i] = nums2[j];
            i++;
        }
        Arrays.sort(nums1);
    }
}
// 08/23/2023 00:29	Accepted	1 ms	41.4 MB	java
// 하지만 결과는 오차범위 내의 동일한 결과

회고:
간단한 방식으로는 풀이 자체는 쉬웠지만 개선점을 생각하고자 하니 어떻게 해야 할지 좀 감을 못 잡겠다.