리트코드 - 88. Merge Sort Array

리트코드 - 88. Merge Sort Array

출처 - https://leetcode.com/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

두 개의 정수 배열 nums1과 nums2가 주어지며, 두 배열은 각각 비내림차순으로 정렬되어 있습니다. 또한, 정수 m과 n이 주어지며, 이는 각각 nums1과 nums2의 요소 수를 나타냅니다.

nums1과 nums2 배열을 하나의 비내림차순으로 정렬된 배열로 합치세요.

최종적으로 정렬된 배열은 함수에서 반환되지 않고, 대신 배열 nums1 내부에 저장되어야 합니다. 이를 위해 nums1의 길이는 m + n이며, 처음 m 요소는 병합되어야 하는 요소를 나타내고, 나머지 n 요소는 0으로 설정되어 무시되어야 합니다. nums2의 길이는 n입니다.

 

의사코드

생략

풀이코드

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

        for (int i = inputIdx; i >= 0; i--) {
            if (m > 0 && (n <= 0 || nums1[m - 1] > nums2[n - 1])) {
                nums1[inputIdx] = nums1[m - 1];
                m--;
            } else {
                nums1[inputIdx] = nums2[n - 1];
                n--;
            }
            inputIdx--;
        }
    }
}

코드설명

문제의 설명에서 nums1 배열에 최종적으로 담아야 한다.

inputIdx는 nums1 배열의 가장 마지막 부분인데 이곳부터 하나씩 담으면 된다.

 

입력되는 배열 부분은 이미 비내림차순(오름차순이나 중복값이 존재하는 차순)으로 정렬이 되어있다.

따라서 m번째 해당하는 nums1 배열 값과, n번째 해당하는 nums2 배열의 값을 비교하여 큰 순서대로 inputIdx에 넣으면 된다.

 

단, 여기서 m이 0인 경우와 n이 0인 경우를 고려해야 하는데

m이 0인 경우(= nums1 배열에서 넣을 값이 아무것도 없는 경우) nums2 에서만 입력되므로 else 에서 처리가 되지만,

n이 0인 경우(= nums2 배열에서 넣을 값이 아무것도 없는 경우)  nums1[m - 1] > nums[n -1]을 해버리면 배열 밖을 벗어나 outOfBound 가 발생한다.

 

따라서 n이 0인 분기를 나누어 n <= 0 조건을 추가해준다.

 

시간복잡도 O(m + n)

공간복잡도 O(1)

 

문제를 풀며 어려웠던 점과 배운 점

easy 문제지만 푸는데 하루 + 반나절이 넘게 걸렸다.

사실 이 문제는 그냥 n번째 부분부터 nums1 배열에 nums2 배열을 추가하고, Arrays.sort를 돌려버리면 바로 해결된다.

그렇지만 이렇게 이미 만들어진 메소드 말고, 앞에서부터 수를 비교하는 로직을 직접 짜서 구현 해보고 싶었다.

첫번째 방법

    for (int i = 0; i < n + m; i++) {
        for (int j = idx; j < n; j++) {
            if (compareTo(nums1[i], nums2[j])) {
                shift(i, nums1);
                nums1[i] = nums2[j];
                idx = j + 1;
                break;
            } else {
            	...
            }
        }
     }
}

    static boolean compareTo(int a, int b) {
        return a >= b;
    }

    static void shift(int idx, int[] arr) {
        int size = arr.length;
        for (int i = size - 1; i > idx; i--) {
            arr[i] = arr[i - 1];
        }
    }

첫번째 방법은 위와같이 복잡한 코드였다.

가장 먼서 생각한 부분은 nums2의 값을 비교해서, 작거나 같은 값이 나오면 배열을 한칸씩 밀어내고 값을 넣는 방법을 생각했었다.

그리고 큰 값이 나오면 뒤에 넣는 방법이다.

 

하지만 인덱스를 벗어나거나, 원하는 값을 제 위치에 넣지 못하거나 하는 등의 무수히 많은 문제가 터졌다.

머리가 굳어서 그런건가?싶어 집에서도 해보고, 카페에 가서도 해보고 4~5시간동안 차가 식는동안 붙잡았는데도 해결이 안나더라..ㅠ.ㅠ

 

결론은 compareTo 메소드에서처럼 단순히 boolean 값으로 분기를 만들려고 하다보니 발생한 문제였다.

 

예전에 별찍기 문제를 풀 때도 이런 문제가 있었던 것 같다.

for문 안에서 관련된 변수를 바꾸면 정말 잘 만들지 않는 이상 문제가 발생한다.

 

두번째방법

두번째는 배열하나를 새로 만들어서 정렬하고, 복사하는 방법이었는데 해보진 않았다.

그럴바엔 Arrays.sort랑 다른게 뭐가 있을까 싶어서라고 생각해서이다.

잠깐 해보다가 문제에서 nums1 배열에 넣는다는 것을 보고 생각을 접었다.

 

 

정리 및 궁금증

이렇게 풀다보니 Arrays.sort는 어떻게 구성되어 있는지 궁금하게 되었다.

 public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

Arrays클래스를 찾아 들어가니 위와 같은 코드로 되어있었다.

매개변수가 여섯개나 되네...

 

다시 DualPivotQuicksort를 들어가봤는데...수 많은 sort가 오버로딩 되어있었다.

 

코드가 어려워서 완벽하게 이해할 순 없지만, 주석을 확인해보면 작은 배열에 대해서는 퀵 정렬을 이용하고, 큰 배열에 대해서는 병합 정렬을 이용하고 있었다.

알고리즘 초기에 배운 정렬들이 이렇게 코드 내부에서 쓰인다는 것을 알게되니 왜 배우는지 필요성에 대해 알게된 것 같다.

 

그리고, 한 문제를 푸는데 너무 시간이 오래걸린다면 그 방법을 너무 고집하지말고 아예 새로운 방법을 찾아보는 게 더 나은 선택일 수도 있을 것 같다.