LeatCode : 88. Merge Sorted Array

문제 링크

Merge Sorted Array - LeetCode

문제 먼저 읽기

• 오름차순으로 정렬된 숫자 배열 2개 nums1, num2 가 주어진다.
• 이 두 배열을 nums1 배열 안에 오름차순으로 합쳐야 한다.
• 현재 nums1은 합쳐질 nums1의 숫자 개수 m과 num2 배열 길이인 n만큼의 길이를 갖고 있고, n만큼 배열 뒷쪽이 0으로 채워져 있다.

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

어떻게 풀까?

• O(n^2) 보다 빠르게 풀기 위해 pointer를 3개 이용해서 O(n)으로 시간복잡도를 줄일 수 있을 것 같다.
• 새로운 배열로 만든다면 코드가 더 간단해지겠지만 num1에 합쳐야 하는 문제라 조금 복잡해졌다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int pointer1 = m -1; // nums1의 포인터. 가장 큰 숫자부터 정렬한다.
        int pointer2 = n -1; // nums2의 포인터.

        int inputPointer = m+n -1; // nums1에서 큰 숫자부터 삽입할 포인터

        while (inputPointer >= 0) { // 삽입하는 포인터가 0보다 더 작게 되면 정렬이 끝낸다.
            if (pointer1 < 0) { // 한쪽 배열이 끝났을 때
                nums1[inputPointer] = nums2[pointer2];
                pointer2 --;
            } else if (pointer2 < 0) { // 한쪽 배열이 끝났을 때
                nums1[inputPointer] = nums1[pointer1];
                pointer1 --;
            } else if (nums1[pointer1] > nums2[pointer2]) { // 큰 숫자를 삽입
                nums1[inputPointer] = nums1[pointer1]; 
                pointer1 --;
            } else {
                nums1[inputPointer] = nums2[pointer2];
                pointer2 --;
            }

                inputPointer --; // inputPointer 를 줄인다.
        }
    }
}

• 결과

<aside> 💡 Success

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Sorted Array. Memory Usage: 41.1 MB, less than 89.09% of Java online submissions for Merge Sorted Array.

</aside>

다른 풀이와 문제 회고

• 다른 코드 예시를 봄며 Runtime과 Memory 효율을 개선할 수 있는 지 확인해보았다.

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

        int[] temp1 = new int[m];
        for (int index = 0; index < m; index++) {
            temp1[index] = nums1[index];
        }

        int i = 0;
        int j = 0;
        int cur = 0;
        while (i < m || j < n) {
            if ((i < m && j < n) && (temp1[i] <= nums2[j])) {
                nums1[cur++] = temp1[i++];
            } else if ((i < m && j < n) && (temp1[i] > nums2[j])) {
                nums1[cur++] = nums2[j++];
            } else if (i < m) {
                nums1[cur++] = temp1[i++];
            } else if (j < n) {
                nums1[cur++] = nums2[j++];
            }
        }
    }
}

• 0부터 포인터를 사용해서 오름차순으로 배열한 예시이다. 새로운 배열을 만들고 num1의 내용을 옮기고 하니 0부터 사용하기 편해졌다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m-1;
        int p2 = n-1;
        for (int i = m+n-1; i >= 0; i--){
            if (p2 < 0) break;
            if (p1 >= 0 && nums1[p1] > nums2[p2]){
                nums1[i] = nums1[p1--];
            } else {
                nums1[i] = nums2[p2--];
            }
        }
    }
}

• 변수 사용을 줄여 코드가 간결해졌다.
• if 중 의미가 중첩되는 부분은 쓰지 않았다.
• 그 외 로직은 비슷한 구조를 가지고 있다.