Week 1-1. [Array / String] 88. Merge Sorted Array

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Merge Sorted Array - LeetCode

두 배열을 merge 하여 오름차순으로 정렬하라.

• 입력
  • nums1 | arrray := nums2까지 merge하여 최종 정렬해야할 배열, | nums1 | == m + n
  • m | int := nums1에서 0이 아닌 원소의 개수, | m | ∈ [0, 200]
  • nums2 | array := nums1에 merge 되어야할 배열, | nums2 | == n
  • n | int := nums2의 길이, | n | ∈ [0, 200]
• 출력
  • nums1 | arrray := nums2까지 merge하여 오름차순 정렬된 배열
• 조건
  • | m + n | ∈ [1, 200]
  • | nums1[i], nums2[j] | ∈ [-10^9, 10^9]
  • 최종적으로 정렬된 배열은 함수로 리턴하거나 출력하지 않는다. nums1 배열 안에 저장되어 있어야 한다.

 

🔎 어떤 식으로 접근했는가?

멘토님께서 1주 차에는 효율적인 알고리즘보다는 주먹구구식으로라도 문제를 풀어내는 게 중요하다고 하셨다.

따라서 단순하게 nums1의 0 자리에 nums2의 원소들을 차례로 대입한 뒤, 오름차순 정렬을 생각했다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

nums1에서 0(=nums2로 채워야 할 원소)의 개수는 n이다.

n번 반복했을 때의 시간복잡도는 O(n) 이고 n은 최대 200이므로 반복문 하나로 해결할 수 있다.

 

📝 의사 코드

for (nums1에서 0이 시작되는 곳부터, nums1 끝까지, 1씩 더해) {
	nums1에서 0 자리에 nums2 원소들을 하나씩 넣는다.
}
nums2를 오름차순 정렬한다.

 

🎯 구현 코드

import java.util.Arrays;
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i = m; i < nums1.length; i++) {
            nums1[i] = nums2[i-m];
        }
        Arrays.sort(nums1);
    }
}

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

for문에서 i가 m부터 nums1.length까지, 즉 (m + n) - m = n 번 반복한다.

따라서 시간 복잡도는 O(n)이다.

공간을 추가로 할당받지 않았으므로 공간 복잡도는 O(1)이다.

 

✍️ 성능 회고

LeetCode 문제에서는 시간 복잡도를 O(m + n) 내로 구현하라고 했다.

따라서 나쁘지 않은 성능을 가져갔다고 생각한다.

 

💡 무엇을/어떻게 개선할 수 있을까?

 

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // variables to work as pointers
        int i = m - 1;
        int j = n - 1;
        int k = nums1.length - 1;

        while(j >= 0){
            if(i >= 0 && nums1[i] > nums2[j]){
                nums1[k] = nums1[i];
                k--; 
                i--;
            } else{
                nums1[k] = nums2[j];
                k--; 
                j--;
            }
        }
    }
}

i는 nums1에서 의미있는(=0이 아닌) 원소의 마지막을 가리키고, j는 nums2의 마지막을 가리킨다.

k는 nums1의 가장 마지막을 가리킨다.

 

nums1[i]와 nums2[j]를 비교하면서 더 큰 값을 k에 넣는다. (이렇게 구현하면 자동으로 오름차순 정렬까지 된다.)

그리고 사용한 포인터(i 혹은 j)의 값을 1 감소시킨다.

 

j의 값이 0보다 크거나 같은 동안 이를 반복한다.

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

nums1 배열에 n + m 개의 원소를 삽입하므로 시간 복잡도는 O(n + m)이다.

공간을 추가로 할당받지 않았으므로 공간 복잡도는 O(1)이다.

 

🛠 내 코드에 적용해보기

 

 

느낀 점

구현은 간단했지만 시간 복잡도와 공간 복잡도를 계산해본 경험이 많이 없어 낯설었다.

앞으로 구현 뿐만 아니라 성능까지 고려하여 코드를 짜는 연습을 해야할 것 같다.