[LeetCode] Merge Sorted Array

두 개의 배열 nums1, nums2 를 nums1 에 하나로 합치는 문제입니다.

두 배열은 오름차순 정렬되어있고, 합쳐진 nums1 도 정렬되어야 합니다.

nums1 은 nums2 의 길이인 n 만큼의 추가 공간이 있으며 해당 공간은 0 으로 채워져 있습니다.

✍풀이

import java.util.Arrays;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // nums2의 요소를 nums1의 뒤쪽에 복사
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        // 전체 nums1 배열을 정렬
        Arrays.sort(nums1);
        // System.out.println(Arrays.toString(nums1));
    }
}

이 코드는 두 개의 정렬된 배열 nums1과 nums2를 병합하는 작업을 수행합니다. nums1 배열의 크기는 m + n이며, 처음 m개의 요소는 nums1에 저장된 값이고, 나머지 n개의 요소는 0으로 초기화된 상태로 남아있습니다. nums2는 n개의 요소를 가진 배열입니다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
        int p1 = m - 1;
        int p2 = n - 1;
        int p = m + n - 1;
        
        // nums1과 nums2의 요소를 비교하여 큰 요소부터 nums1의 뒤쪽에 채움
        while(p1 >= 0 && p2 >= 0){
            // System.out.println("p1, p2, index : " + p1 + ", " + p2);
            // System.out.println("p1, p2, array = " + nums1[p1] + ", " + nums2[p2]);
            // System.out.println("배열 길이 : " + p); 
            if(nums1[p1] > nums2[p2]){
                nums1[p--] = nums1[p1--];
            }else{
                nums1[p--] = nums2[p2--];
            }
        }
         
        // nums2에 남은 요소가 있다면 채워넣음
        // nums1의 남은 요소들은 이미 제자리에 있기 때문에 따로 처리할 필요가 없습니다.
        while(p2 >= 0){
            nums1[p--] = nums2[p2--];
        }
    }
}

배열의 뒤에서부터 큰 요소를 하나씩 채우는 방법을 사용하면 정렬 없이도 효율적으로 병합할 수 있습니다.

배열의 뒤부터 비교해가며 넣어줍니다.

p1 또는 p2 가 0 이 되고 나면 나머지 하나가 0 이 될때까지 배열을 채워야 합니다.

p1 은 이미 배열에 채워져 있기 때문에 p2 가 0 이 될 때까지만 값을 넣어주면 됩니다