LeetCode 88: 정렬된 배열을 뒤에서부터 합치기

문제에서 말하는 유효한 길이

정렬된 두 배열 nums1, nums2를 합쳐 nums1 안에 저장하는 문제입니다. 새 배열을 반환하지 않습니다. nums1의 실제 길이는 m + n이지만 처음부터 유효한 값은 앞의 m개뿐입니다. 뒤의 n칸은 nums2를 넣기 위한 공간입니다.

처음에는 m이나 n이 0인 예시가 헷갈렸습니다. m = 0인데 nums1에는 0이 들어 있고 n = 0인 nums2는 빈 배열이었기 때문입니다. 예시를 보면서 배열의 실제 길이와 유효한 값의 개수를 나눠 생각했습니다.

문제에서는 O(m + n) 시간에 합치는 방법도 추가로 요구합니다.

빈칸에 복사한 뒤 정렬했습니다

첫 번째 예시에서 nums1의 길이는 6이지만 m은 3입니다. 앞의 세 값은 유지하고 뒤의 세 칸에 nums2를 넣은 다음 정렬하면 될 것 같았습니다.

n = 0이면 복사할 값이 없으므로 nums1을 그대로 둡니다.

m = 0이면 nums1에 있던 값은 유효한 데이터가 아닙니다. 첫 칸부터 nums2로 채우면 됩니다.

복사 위치를 m부터 시작해 m + n 직전까지 반복하도록 잡았습니다.

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)이라고 적었습니다. 하지만 배열 두 개를 합쳐 정렬한다는 이유만으로 두 길이의 곱이 되지는 않습니다.

큰 값부터 뒤에 넣었습니다

두 배열은 이미 정렬되어 있습니다. 각각의 가장 큰 값을 비교해서 뒤쪽부터 넣으면 되지 않을까요? 두 배열에서 마지막 유효한 값끼리 비교해 더 큰 값을 nums1의 맨 뒤에 넣도록 바꿨습니다.

indexM과 indexN은 각 배열에서 아직 옮기지 않은 값 중 마지막 것을 가리킵니다. position은 값을 넣을 위치입니다. nums1 쪽 값이 더 크면 그 값을 뒤로 옮기고 그렇지 않으면 nums2의 값을 넣습니다. 값을 사용한 쪽의 인덱스와 저장 위치를 한 칸씩 줄였습니다.

뒤에서부터 채우면 nums1에서 아직 비교하지 않은 값을 덮어쓰지 않습니다. nums2를 모두 옮긴 뒤에는 nums1에 남은 값이 이미 제자리에 있으므로 반복을 끝낼 수 있습니다.

각 값을 뒤로 옮기며 인덱스를 줄이므로 O(m + n)이고 별도 배열을 만들지 않습니다.

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--];
            }
        }
    }
}