LeetCode 88 Merge Sorted Array

nayu1105·2023년 8월 22일

leetcode 알고리즘

LeetCode

목록 보기

3/28

LeetCode 88 Merge Sorted Array 풀러가기

문제

오름차순으로 정렬된 int배열이 두개 주어진다. (nums1, nums2)

nums1에는 m개의 숫자와 n개의 0이 있고, nums2 에는 n개의 숫자가 있다.

nums1과 nums2배열을 병합하여 오름차순으로 정렬된 배열을 만들면 된다.

단, 오름차순으로 정렬된 배열은 nums1에 저장되어야 한다.

문제 분석

첫번째 시도 (소요 시간 3분)

두 개의 배열이 모두 오름차순으로 정렬되어 있으니 따로 정렬할 필요는 없었다.

m+n 크기인 int 배열 nums3을 만들어서 각 배열을 순회하며 둘 중 작은 값을 인덱스 0번부터 순서대로 넣는 알고리즘을 짰다.

시간복잡도는 O(n)이니, 괜찮다고 생각했다.(n은 문제에서 m+n이다)

코드

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums3 = new int[m+n];
        int nums1_index = 0;
        int nums2_index = 0;
        
        for(int i=0; i<m+n; i++){
            if(nums1_index==m){
                nums3[i] = nums2[nums2_index++];
            }else if(nums2_index==n){
                nums3[i] = nums1[nums1_index++];
            }else{
                if(nums1[nums1_index]>nums2[nums2_index]){
                    nums3[i] = nums2[nums2_index++];
                }else{
                    nums3[i] = nums1[nums1_index++];
                }
            }
        }

        nums1 = nums3;
    }
}

결과 : 실패

테스트 케이스 3개 중에 2개가 틀렸다.

의심이 된건, nums3라는 새로운 배열을 할당하고 마지막에 nums1 = nums3 라고 적으면서 배열의 주소를 바꾼 것인데, LeetCode는 이 꼼수를 안쳐주는 것인가? 라는 생각이 들었다.

혹시나 해서 코드를 복사해서 IDE로 실행 시켜보니 배열이 잘 들어갔다.

그러던 중 테스크 케이스를 유심히 살펴보니, num1의 값이 Input값 그대로임을 확인했다. 그래서 num1의 배열 결과값을 확인하는 코드, 즉 LeetCode에서 정답을 확인하는 코드가 이 함수를 호출한 후 num1을 확인하는 것이라면, 지역변수인 nums3는 영향을 주지 않을 것이고, nums1은 예전 결과 그대로라는 것을 알아냈다.

~~기본적인 얉은 복사, 깊은 복사를 까먹다니 다시 공부해야겠다.....~~

두번째 시도 (소요 시간 3분)

nums1에 바로 저장을 시켜야 한다면, 이미 크기가 m+n이니 모든 숫자를 nums1에 넣고, Array.sort()를 사용하자고 생각했다.

Arrays.sort()의 시간 복잡도는 평균 O(nlog(n)), 최악은 O(n^2)이였다.

문제에서 m+n이 최대 200이라고 해서, 200*200 = 40,000 이니까 그 정도 연산이면 괜찮겠다고 결론내렸다.

코드

import java.util.*;
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index =  0;
        for(int i=m; i<m+n;i++){
            nums1[i] = nums2[index++];
        }

        Arrays.sort(nums1);
    }
}

결과 : 성공

시간	메모리
1ms	41MB

Runtime

런타임이 생각보다 길어서 역시 이렇게 막무가내로 짜는건 좋지 않다고 느껴졌다.

Memory

메모리는 다른사람들과 비슷했다.

좋은 코드일까?

지금은 m+n이 200보다 작았기 때문에 Arrays.sort가 가능해지만, 이것이 매우 커지면, 최악의 시간복잡도 O(n^2)이 생길 수 있기 때문에 좋지 못한 방법같다.

만약 m+n이 1000 이라면 1000,000이 될 것이고, 1000,000 이라면 1000,000,000,000이 될 것이다. 이것이 더 커지면 커질 수록 더 최악의 상황이 발생할 것 같았다.

세번째 시도 (소요시간 3분)

마지막 시도는 다른 사람이 제출한 코드를 보며 아이디어를 얻고 새로 짰다.
nums1의 m+1부터 m+n까지는 0으로 채워져있다. 그렇기 때문에 뒤쪽 배열은 쓸모 없는 값이기 때문에 뒤쪽부터 채워나가면 되겠다고 생각했다.
nums1의 m+n-1 인덱스부터 nums1의 m-1 인덱스, nums2의 n-1 를 비교하며 채워가도록 했다.

코드

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

        for(int i=m+n-1; i>=0; i--){
            if(index1==-1){
                nums1[i]=nums2[index2--];
            }else if(index2==-1){
                nums1[i]=nums1[index1--];
            }else{
                if(nums2[index2]>nums1[index1]){
                    nums1[i]=nums2[index2--];
                }else{
                    nums1[i]=nums1[index1--];
                }
            }
        }
    }
}