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

88. Merge Sorted Array

⭐ 문제

숫자로 이루어진, 오름차순으로 되어있는 두 배열 nums1과 nums2 그리고 각각의 길이를 나타내는 m, n이 주어져있습니다. 두 배열을 병합하고 오름차순으로 정렬하세요

🤔 고려해야할 사항

1. nums1에 병합해야 합니다.
2. nums2가 들어가야할 nums1의 배열의 요소는 0으로 설정되어 있습니다. 병합시에 0은 무시하고 병합되어야 합니다.

✍️ 의사 코드

1. nums1에 nums2를 넣기
2. nums1을 오름차순으로 정렬

✅ 나의 풀이

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n); 
        Arrays.sort(nums1); 
    }
}

🖥️ 결과

Runtime 1ms

🤔 추가 질문

O(m + n)의 시간 복잡도를 가진 알고리즘으로 설계 할 수 있나요?

😰 나의 풀이 되돌아보기

1의 System.arraycopy(nums2, 0, nums1, m, n)의 시간 복잡도는 O(n)인데 2의 Arrays.sort(nums1)의 시간복잡도는 O(m * log m)의 복잡도를 가집니다. 즉 총합 시간 복잡도는 O(n + m * log m) 입니다.

🔥 개선을 위한 고민

• 문제를 차근차근 다시 읽어보았는데 nums1과 nums2가 이미 오름차순으로 정렬되어있다는 점이 눈에 띄었습니다. 이를 활용하여 시간복잡도 O(m * log m)의 Arrays.sort(nums1)를 사용하지 않고 해결한다면 더 빠르게 수행할 수 있을거 같습니다. 이를 위해서 1의 System.arraycopy가 아닌 전체적으로 새로운 풀이의 필요성이 느껴졌습니다.
• 1,2 2개의 과정으로 나누는 것이 아니라 하나의 동작으로 하려면 어떻게 해야하는지 고민해 보았습니다. 그 결과 정렬되어있는 두개의 정렬을 값을 비교하면서 알맞은 위치에 넣어준다는 하나의 동작으로 하면 어떨까라는 발상이 떠올랐습니다.
  이를 위해선 이전에 부트캠프에서 사용하였던 두개의 배열을 동시에 다루는 투포인터 알고리즘이 적합한거 같았습니다.
• 투포인터 알고리즘으로 두 배열의 첫값부터 비교하면서 풀어볼려고 하니 생각되로 잘 되지 않았습니다. 그러던 중 고려해야할 사항에서 nums1의 배열 끝부분에는 nums2가 들어가기 위해 0의 값으로 입력되어 있다는 제약조건이 떠올랐습니다. 그렇다면 끝 값부터 정리해나가면 될거 같아서 이를 통해 새로운 풀이를 작성해 보았습니다.

✍️ 개선한 의사 코드

1. 투포인터 알고리즘을 위한 두가지 포인터 pt1,pt2에 각 배열의 마지막 인덱스를 주입
2. pt2가 0이상인 경우 포인터가 지정한 인덱스 값을 계속하여 비교
   2-1. 만약 pt1에 해당하는 값이 더 크거나 같다면 해당 값을 nums1의 마지막 값 즉 pt1 + pt2 + 1의 인덱스값에 넣기 그리고 pt1 감소
   2-2. 그외의 경우 즉, pt2에 해당하는 값이 더 큰 경우에는 해당 값을 nums1의 마지막 값 즉 pt1 + pt2 + 1의 인덱스값에 넣기 그리고 pt2 감소

✅ 개선한 풀이

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        pt1 = m;
        pt2 = n;
		
        while (ptr1 >= 0 && ptr2 >= 0) {
            if (nums2[ptr2] > nums1[ptr1]) {
                nums1[ptr1 + ptr2 + 1] = nums2[ptr2];
                ptr2--;
            } else {
                nums1[ptr1 + ptr2 + 1] = nums1[ptr1];
                ptr1--;
            }
        }
        
        while (ptr2 >= 0) {
            nums1[ptr1 + ptr2 + 1] = nums2[ptr2];
            ptr2--;
        }
    }
}

🖥️ 결과

Runtime 0ms

이전 풀이의 1ms에서 0ms로 줄어든 것을 확인할 수 있었습니다.

👨‍💻 느낀 점

문제를 처음 봤을땐 단순하게 배열을 합쳐서 정렬해야겠다는 생각만 하였습니다. 필요한 기능을 구현하고 나서 단순하게 기능구현에만 성공했다는 수준에서 만족하였습니다. 이러한 태도는 지금까지 웹개발에서도 똑같이 이루어진거 같습니다. 필요한 서비스를 구현하고 나서 서비스의 구현에만 집중하였지 효율적인 서비스의 제공 측면에선 생각해보지 않았습니다. 앞으로 알고리즘을 공부해나가면서 그러한 태도에서 벗어나고 이를 위한 역량을 키워나가는 계기가 되었으면 좋겠습니다.