[알고리즘 / 초급] merge sort 중 merge 응용

https://leetcode.com/problems/merge-sorted-array/

리트코드의 위의 문제 풀이이며, 아래의 이론을 기반으로 코드를 구성하였습니다.

https://www.youtube.com/watch?v=0AIZBg3yFL0&list=PLRJdqdXieSHN0U9AdnmwD-9QcR9hmw04d&index=72&ab_channel=Damn%21ILoveData

문제 코드

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
    }
}

개념설명 및 문제

위 링크에서 핵심 개념 부분입니다. 필요없으신분들은 스킵하시면 됩니다. 

여기서 해결해야할 문제는 nums1안에 nums1 nums2를 정렬해서 넣는것 입니다. 제약조건은 개념설명 이후에 이어집니다.

핵심개념

머지소트는 위와같은 세가지 과정으로 이루어져 있습니다. 

1번은 base case입니다. 리스트의 길이가 0 또는 1이면 정렬할게 없기 때문에 그 값을 반환합니다.

2번은 나누는 과정입니다. list길이가 1개 초과이면, 1개가 될때까지 나눕니다.

3번은 각각 나뉜 리스트를 합치면서 정렬하는 것입니다. 이때, 각 첫번째 값끼리 비교합니다. 더작은 값을 먼저 오게 한 후, 해당 리스트의 인덱스를 증가시킵니다. 이 과정을 반복하여 한쪽리스트가 비게 된다면, 나머지 다른쪽 리스트의 남은 값을 뒤에다가 붙입니다. 

그림으로 보면 위와같이

 위 문제는 이중 오로지 merge에 대한 부분만 다룹니다

Merge 코드

아이디어는 위에서 설명한 바와 같이, 나뉜 두 리스트의 각각 첫째 값을 비교한후, 더 작은 값을 새로 merge될 리스트에 넣고, 해당 리스트의 인덱스를 증가시키는 것 입니다. 이 과정을 반복한 후, 한쪽 리스트가 empty가 된다면 다른 리스트를 merge 리스트뒤에 붙이면 됩니다.

파이썬 기준 코드는

def merge(left,right):
	result = []
    i,j =0,0
    while i < len(left) and j <len(right):
    	if left[i] < right[j]:
        	result.append(left[i])
            i += 1
		else:
        	result.append(right[j])
            j += 1
	while (i < len(left)):
    	result.append(left[i])
        i += 1
    while (j < len(right));
    	result.append(right[j])
        j += 1
    return result

 

다시 메인 문제로 돌아와서... 변수 및 제약조건

- List int: nums1, nums2

- int : m,n

nums1,2는 오름차순으로 정렬되어 있습니다. 

m,n은 각각 nums1과 nums2안에 있는 element의 갯수를 뜻합니다.

 모든 기능이 끝난 후, 값을 따로 반환하는 것이 아는 nums1안에 sorted list가 들어가는 방식입니다. 이를 위해 nums 1의 길이는 m+n으로 되어 있으며, m만큼의 크기엔 정렬된 값이 들어가 있고, 그 뒤엔 0만 들어가 있습니다. 따라서 0은 무시해야 하는 값입니다.

예시1)

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: merge 하려는 배열은 [1,2,3] 과 [2,5,6] 임.
머지 결과는 [1,2,2,3,5,6] 이며 nums에서 가져온 값들을 볼 수 있음.

 

예시2)

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

 

예시3)

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

 

제약조건

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

 

풀이 아이디어

nums1 = [1,2,3,0,0,0]

nums2 = [2,5,6]

m,n = 3

으로 가정하고 하겠습니다.

1. nums1의 element를 뒤로 쉬프팅 시킵니다. 즉 앞에 0이 오도록 합니다
   1. [1,2,3,0,0,0] -> [0,0,0,1,2,3]
   2. 사실 메모리스페이스 낭비가 있기 때문에 굳이 0으로 안바꿔줘도 되지만 이해를 위해서 0으로 바꿧습니다
2. 변수는 t, i,j를 도입하며 각각 sort된 값이 들어갈 자리(target), nums1의 현재 인덱스, nums2의 현재 인덱스 입니다.
   1. nums1을 shifting 했기 때문에 i = n 부터 시작합니다
3. 이 변수를 적용하여 merge 기능을 실행시킵니다.

이렇게 글로만 있어서 조금 이해가 안갈수도 있지만, 노트에 적으면서 하신다면 좀더 이해가 잘 되시리라 생각합니다.

 

결과코드

직접 풀어보실 분들을 위해 접은글 처리 하였습니다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int t=0,i=m,j=0;
        for (int k = m+n-1;k>=n; k--){
            nums1[k] = nums1[i-1];
            i--;
        }
        i=n;
        while(i<nums1.length && j<nums2.length){
            if(nums1[i]<=nums2[j]){
                nums1[t] = nums1[i];
                i++;
            }else{
                nums1[t] = nums2[j];
                j++;
            }
            t++;
        }

        while(i< nums1.length){
            nums1[t] = nums1[i];
            i++;
            t++;
        }

        while(j< nums2.length){
            nums1[t] = nums2[j];
            j++;
            t++;
        }
    }
}

 

위의 코드 실행시 전체 중 순위

runtime은 가장 빠른 수준

메모리 사용량도 준수

 MIT수업 내용을 거의 가져다 썼기 때문에 상당히 빠른 결과를 만들어 낼 수 있었습니다.

 

끝