[Leetcode Top Interview 150] 88. Merged Sorted Array

<문제> 난이도 : easy 

문제 링크

- num1, num2라는 두개의 int 배열이 있다 (non-decreasing order)

- m과 n은 각각 배열의 정렬하고자 하는 범위를 뜻함

- 요구사항

   num1과 num2를 하나의 배열로 병합하라 (non-decreasing order)

   - 함수에 의해 리턴되는 것이 아닌, 기존의 num1 변수에 저장되게끔 구현하기

 

1. 접근법

- 배열의 정렬 및 병합을 하기 위해서 각각의 원소들에 접근하여 크기를 비교한 후,
   nums1의 원소가 크면 한칸씩 미뤄주고, 삽입을 시도

   nums2의 원소가 크면 배열 유지

 

- m, n값까지만 병합의 대상이 되는 배열이므로 삽입 필요 여부에 따라 m 혹은 n 값을 줄여가면서 반복함

- nums1이 target array이므로, pointer라는 변수를 두어 target array를 업데이트함

- num2는 source array이므로, 0~n값을 활용하여 source array로 사용함

 

2. 의사코드

if (n == 0) 
  리턴 (작업 필요없음)
  
if (m == 0) 
  nums2 배열을 nums1에 붙여넣기
  
while (
1. target array의 원소를 가리키는 포인터가 m+n값보다 작고
2. num1의 병합 대상범위를 뜻하는 m값까지만 포인터 돌리기
3. num1의 병합 대상범위를 뜻하는 n값까지만 포인터 돌리기 ) {
  if (현재 포인터가 가리키는 target array의 원소가 nums2 원소보다 크면) {
    // 삽입이 필요함 -> 현재 포인터로부터 뒷쪽으로 한칸씩 미루기 -> 삽입할 인덱스 비우기
    // 삽입
  }    
}

if (반복문을 다 돌렸는데 n값 까지의 source array가 남아있다면) {
    // target array의 반복문 모두 돌고 현재 가리키는 포인터 인덱스에 남아있는 nums2 배열을 이어붙이기
}

 

3. 구현 코드

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }

        if (m == 0) {
            for (int i = 0; i < n; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }

        int totCnt = m+n;
        int mCnt = 0;
        int nCnt = 0;
        int pointer = 0;

        while (pointer < totCnt && mCnt < m && nCnt < n) {
            if (nums1[pointer] > nums2[nCnt]) {
                for (int i = totCnt-1; i > pointer; i--) {
                    nums1[i] = nums1[i-1];
                }

                nums1[pointer] = nums2[nCnt++];
            } else {
                mCnt++;
            }

            pointer++;
        }

        if (nCnt < n) {
            for (int i = nCnt; i < n; i++) {
                nums1[pointer++] = nums2[i];
            }
        }
    }
}

 

4. 시간복잡도, 공간복잡도 예상

- 시간복잡도 : O((m+n)^2)

  while 문에서 for문이 돌기 때문에 worst case는 (m+n) * (m+n)

- 공간복잡도 : O(1)

  상수 공간을 사용하므로 totCnt, mCnt, nCnt, pointer 하나씩만 들어감

  (파라미터로 받은 변수는 공간복잡도에 포함되지 않음)

 

5. 개선점

- 시간복잡도를 O(m+n)으로 해야 할 것 같다

  어떻게 하면 삽입을 위해 한칸씩 미루는 연산을 하지 않을 수 있을까

  잘 생각이 나지 않아 인터넷에서 서칭을 하였다

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m + n - 1;
        int i = m - 1;
        int j = n - 1;

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

        while (j >= 0) {
            nums1[index--] = nums2[j--];
        }
    }
}

(출처 : https://bcp0109.tistory.com/269)

이미 num1, num2가 정렬상태이며, 추가공간 없이 풀어야 하므로 뒤에서부터 접근하여 병합하여 푸셨다

이렇게 하면 삽입을 위한 뒤로 미루는 연산이 필요 없어지므로 O(m+n)으로 연산이 가능하다 (와우)

 

6. 회고

- 배운점

  정렬 시에 원소를 뒤에서 접근해서 푸는 생각을 하지 못했다

  일단 문제에서 전제조건으로 정렬된 배열을 제공한다

  또한 num1의 길이가 m+n이므로 m = 1, n = m-1 인 경우가 생기더라도 m값이 overwrite되는 경우는 생기지 않는다

 

풀면서, 분명히 내 코드가 최적화되지 않은 코드는 직관적으로 알고 있었다..

푸는것에 급급해서 성능이 좋지않은 코드를 내었다.

현재 다른 방법이 전혀 떠오르지 않는다. 뒤로 접근해서 푸는 방법을 전혀 생각하지 못할정도로 여유가 없다

일단 개선해야 할 점은 알고리즘에 조금 더 친숙해지도록 해야겠다 느꼈다. 그러려면 시간을 들여야 하고 책을 읽어야 한다

할게 많지만 우선순위를 올려서 매일 2문제씩 해야겠다 생각하였다

 

7. 챌린지를 시작하고 나서 느끼는 점

첫 챌린지를 시작하고 나서 거의 반년만에 알고리즘 문제를 풀었다. (사이드 프로젝트 하느라 바빴다는 변명을.. 열심히해야지)

감이라는 것이 없는 상태에서 풀려니 정말 막막했다. 잘 떠오르지도 않고 생각만 많고 코드 한줄을 적는데 답답하고..

이게 맞나 싶은 생각.. 생각의 힘이 약해졌다는.. 구조화하는데 시간이 오래걸린다

 

아무튼 계속해서 삽질하고 테스트하고 풀어서 3시간만에 Accept를 받았다.

easy 문제여서 전혀  잘했다 할수 없지만 오랜만에 푼 내자신이 모든 과정을 자신의 생각으로만 풀었다는 것에 일단 격려를 해주어야겠다