[LeetCode/JAVA] 88. Merge Sorted Array

문제

감소하지 않는 순서로 정렬된 배열 nums1과 nums2이 주어지고, 각각의 배열에서 유효한 요소의 개수를 나타내는 m과 n이 주어진다.
그리고 이 배열을 감소하지 않는 순서로 하나의 배열로 합쳐야한다.
최종적으로 배열은 함수에 의해 반환되지 않고 배열 nums1 내부에 저장되어야하며, nums1의 길이는 m+n이 되어야한다.
m은 합쳐져야하는 요소의 수를, n은 0으로 설정되어있다면 무시해야한다. nums2의 길이는 n을 가진다.

일단 전체적인 내용으로 nums1이란 배열에 정렬해서 저장을 해야하고, 길이는 m+n이 되게 해야한다는 것 같다.
그렇다면 마지막 문장의 의미는 무엇일까?
문제의 예시 2번에서는 nums2의 길이 n=0이라면 nums2는 비어있는 배열이고, 예시 3번에서는 nums1의 길이 m=0이라면 0이라는 요소가 존재한다.
이를 통해서 m=0이라면 nums1의 내부 요소는 무시하고 n=0이라면 nums2라는 배열 자체를 무시해야한다는 의미로 일단 이해하고 넘어갔다.

제한

의도

O(m+n)의 시간내에 동작하는 알고리즘을 생각해낼 수 있는가?

해결

가장먼저 문제에 대한 고민이다.

예시 1번을 보면 nums1의 실제 길이는 6인데 m의 값은 3이다. nums2의 실제길이는 3인데 n도 똑같은 값이다.
결과로 나온 값은 정렬된 값임과 동시에 의미없던 0이 제외되어있다.

nums1의 유효한 값의 개수가 3개이고 다음에 오는 요소들 위치에 nums2를 넣고 정렬을 하면 되는건가?

이러한 가설을 생각하고 다른 예시를 살펴봤다.

예시 2번의 경우 nums1의 불필요한 요소가 없으므로 nums1의 배열 자체를 사용하고, nums2의 배열의 내용이 없다.

예시 3번의 경우에는 nums1은 의미없는 요소가 포함된 채 nums2의 요소를 대입하면 된다.

그렇다면 nums1의 요소가 유효하다면? -> nums1의 유효한 값 까지 유지한다. -> 필요없는 요소부터 nums2로 대체한다.

다음 이미지와 같이 생각해봤다.

시작 index 값을 m으로 시작해서 m+n까지 반복으로 입력한 뒤 정렬을 한다.

만약 m과 n의 값이 하나라도 0일 경우에는?

위와 같이 for문을 통해 배열 범위의 문제를 해결할 수 있다.

따라서 다음과 같이 코드를 작성했다.

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

        Arrays.sort(nums1);
    }
}

제출 결과는 다음과 같았다.

일단 확실하게 정렬 하는 방식은 아닌거같다.

이미 정렬을 하는 방법에서 O(m * n)이 되어버리므로 효율이 좋지 못했다.

그렇다면 nums2의 요소를 nums1 요소에 입력할 때 인덱스를 지정해서 입력해보자

이미 정렬되어있는 배열들이며 nums1이 유효하지 않은 부분을 nums2로 채우면서 순서를 정렬해야한다.

nums2의 가장 큰 요소와 nums1의 가장 큰 요소를 비교해서 위치를 정해주는 방식이면 되지 않을까?

이미 nums1보다 큰데 nums2가 가장 큰 값이면 nums1의 배열의 가장 뒤에 위치하게 될 것이다.

nums1의 가장 마지막 인덱스를 시작위치로 해서 nums2의 가장 마지막 요소를 nums의 가장 큰 값과 비교하면서
만약 nums2의 요소가 더 크다면 해당 위치에 넣고
만약 nums2의 요소가 더 작다면 nums1의 가장 큰 값을 해당 위치에 넣는다 그리고 비교 대상을 nums1의 두 번째로 가장 큰 값과 비교한다.
만약 nums2의 요소가 nums1의 요소와 같다면 작을 대와 마찬가지로 해당위치에 넣고 비교대상을 변경한다.

그런데 여기서 이전 사진의 마지막 연산의 설명과 같이 2와 3 사이에 입력을 해줘야 하므로 nums1이 더 클 경우가 먼저 나타나므로 nums1의 위치를 해당 위치에 이전 시켜주고 다음 연산을 진행해준다.

동시에 한번 연산된 인덱스들의 경우 증감 연산자를 통해 -1 처리를 해주고 이에 따른 범위의 제한을 해줬다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int indexM = m - 1;
        int indexN = n - 1;
        int position = m + n - 1;

        while(indexN >= 0){
            if(indexM >= 0 && nums1[indexM] > nums2[indexN]){
                nums1[position--] = nums1[indexM--];
            } else {
                nums1[position--] = nums2[indexN--];
            }
        }
    }
}