[LeetCode] 88번(Merge Sorted Array)

 

필자는 자바 스프링 기술스택으로 백엔드 취업을 준비하고 있습니다.

기존에는 파이썬으로 코딩테스트를 준비했지만, 부쩍 자바로 시험봐야 하는 곳도 늘어나고 무엇보다 코딩테스트를 준비하며 자바에 대한 문법과 이해를 높이기 위해 자바로 다시 코딩테스트를 준비하려고 합니다.

때문에 아직 코드가 조금 미흡하더라도 이해해주시길 바랍니다.

 

---

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

Merge Sorted Array - LeetCode

---

 

😀 문제 설명

• 2개의 배열 nums1, nums2 이 오름차순으로 정렬되어 주어진다.
• 각 배열의 원소 수를 나타내는 2개의 정수 n, m 이 주어진다.
• 두 배열을 병합해 오름차순으로 정렬하되, nums1 에 병합해야 한다. 즉 nums1 의 원소의 개수는 n+m 이다.

 

😃 문제 해결

• m 개의 수만큼 정렬되어 있는 nums1의 뒤에 있을 나머지 빈 원소들을 nums2 원소들로 바꿔준다.
• 단 nums2 의 인덱스를 초과해 접근할 수 있기 때문에 (그럴 일은 없겠지만) 그럴시 편한 디버깅을 위해 예외처리를 하나 추가한다.
• 정렬한다.

 

😁 시간복잡도

O(n) + O(n^2) = O(n^2) => 최악의 경우

n의 최대 개수는 200이므로 문제가 없다.

 

 

😆 공간복잡도

추가로 할당하는 변수는 int 형 정수 하나이기에 문제가 없다.

 

 

😄 정답

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = 0;
        for(int i = m; i < m+n; i++) {
            if(p>=n) {
                throw new RuntimeException("배열 인덱스 에러");
            }
            nums1[i] = nums2[p];
            p++;
        }

        Arrays.sort(nums1);
    }
}

 

---

💊 개선해보기

1. Collections.sort() 사용해보기

- Collections.sort() 경우 Arrays.sort() 와는 달리 삽입 병합 정렬을 사용하기 때문에 최악의 경우 시간복잡도가 O(nlogn) 이다. O(n^2)의 시간복잡도를 가지는 Arrays.sort() 보다 좋은 성능을 낼 수도 있다.

 

2. Arrays 라이브러리 사용하지 않고 순수하게 구현해보기

처음에 내린 문제접근법이 비교적 여유로운 제한 범위를 가지고 있었기 때문에 별다른 구현 없이 외장함수를 사용할 수 있었다.

하지만 해당 문제의 좋은 코드들을 보니 라이브러리를 사용하지 않고 일일히 포인터를 통해 구현했다.

사실 어느 방법이 좋은 방법인지는 모르겠다. 허용된 함수 내에서는 외부 소스도 올바르게 사용하는 능력 또한 코딩테스트에서 요구하는 능력이 아닐까 하는 생각이 들었기 때문이다.