[Top Interview Questions] 88. Merge Sorted Array

정답)

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # nums1을 선형할 인덱스
        i = m - 1
        
        # nuns2를 선형할 인덱스
        j = n - 1
        
        # nums1에 새롭게 추가될 자리의 인덱스
        k = m + n - 1

        # nums1과 nums2 모두 선형할 원소가 존재할 때
        while i >= 0 and j >= 0:
            if nums2[j] > nums1[i]:
                nums1[k] = nums2[j]
                j -= 1
            
            # nums2[j] <= nums1[i]
            else:
                nums1[k] = nums1[i]
                i -= 1
                
            k -= 1

        # nums2에 가장 작은 원소들이 존재할 때
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1

 

참고자료: PratikSen07

문제)

문제출처

 

오름차 순으로 정렬된 정수 배열 nums1, nums2 와 각각에 존재하는 원소들의 개수 m, n이 주어집니다.

오름차 순으로 두 배열을 병합하여 nums1 안에 정렬하시오.

 

이 문제는 어떠한 배열을 리턴하는 것이 아닌 nums1 배열을 정렬시키기만 하면 됩니다. 이를 위하여 nums1의 전체 길이는 m+n 입니다. nums1 안에 존재하는 원소들 m개를 제외한 n개의 원소들은 0으로 채워져 있습니다.

 

최종적으로는 이 0들 대신 nums2의 원소들이 nums1 안에 병합되어 모든 원소들이 오름차 순으로 정렬되어 있어야 합니다.

 

예시 1)

nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3

nums1 = [1, 2, 2, 3, 5, 6]

 

예시 2)

nums1 = [1], m = 1, nums2 = [], n = 0

nums1 = [1]

 

예시 3)

nums1 = [0], m = 0, nums2 = [1], n = 1

nums1 = [1]

 

제한)

nums1의 길이 = m+n

nums2의 길이 = n

0 <= m, n <= 200

1 <=  m + n <= 200

-10^9 <= nums1[i], nums2[j] <= 10^9

풀이)

기본원리)

nums1과 nums2를 비교하여 큰 숫자들부터 nums1의 오른쪽에 넣어줄 것입니다.

 

만약 nums2에 숫자가 남아있다면 nums1의 남는 자리에 차례대로 nums2의 숫자들을 넣어줍니다.

왜 큰 숫자들 부터?)

작은 숫자들 부터 넣는게 본능적일 수도 있습니다. 왼쪽에서 오른쪽으로 가는게 자연스러우니까요.

 

하지만 이미 nums1의 왼쪽에는 원소들로 가득 차 있는데 거기서 하나하나 비교 하며 원소들을 오른쪽으로 밀어주다 보면 코드가 너무 복잡해집니다.

 

그래서 이미 빈 칸들이 있는 nums1의 오른쪽에서부터 시작해 큰 숫자들 부터 넣어주는 것이죠.

 

큰 숫자들부터 넣으면 원소 간의 위치를 계속 바꾸어줄 필요가 없습니다

인덱스 설정)

총 3개의 인덱스들이 필요합니다.

 

nums1의 실제 원소들을 선형할 인덱스 i.

nums2의 원소들을 선형할 인덱스 j.

nums1에 새롭게 추가해줄 원소들을 넣어줄 자리들을 선형할 인덱스 k.

 

실제로 비교할 원소들은 [i]와 [j]이고

k는 그저 둘 중 더 큰 원소를 넣을 자리를 표시합니다.

 

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = m - 1
        j = n - 1
        k = m + n - 1

원소들을 비교, 추가)

두 원소들을 비교하기 위해선 두 배열 모두 원소가 있어야겠죠?

 

그래서 두 배열의 실제 원소 인덱스를 나타내는 i와 j가 둘 다 0보다 크거나 같을때 비교를 시작합니다.

두 원소들을 비교하여 더 큰 원소를 nums1의 k 자리에 추가하고 인덱스들을 업데이트 해줍니다.

 

예를 들어 nums2[j]가 nums1[i]보다 클 때 nums1의 k 자리에 nums2[j]를 추가해주고 j를 j-1로 업데이트 해줍니다.

j 자리의 원소를 추가해줬으니 다음 원소를 비교할 준비를 하는 것이죠.

 

그리고 nums1의 k 자리 또한 이제 원소가 존재하기 때문에 k-1로 업데이트 해줍니다.

 

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = m - 1
        j = n - 1
        k = m + n - 1

        while i >= 0 and j >= 0:
            if nums2[j] > nums1[i]:
                nums1[k] = nums2[j]
                j -= 1
            else:
                nums1[k] = nums1[i]
                i -= 1
            k -= 1

nums2의 원소가 전부 추가되지 않았다면)

위 while문이 끝나도 nums2에 아직 추가되어야 하는 원소가 남아있을 수도 있습니다.

만약 i가 -1이 되고 j는 아직 0 이상이라면 추가되어야할 원소들이 남은거죠.

 

nums1의 원소들이 전부 검색되고 nums2의 원소들이 남아있는 경우에는 한 가지 특징이 있습니다.

바로 nums2에 남아있는 원소들이 nums1[0] 보다 작은 경우 입니다.

 

i = -1 / j = 0 / k = 0

그러므로 nums2에 남아있는 원소들을 그저 차례대로 nums1의 k자리에 추가해주시면 되겠습니다.

 

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = m - 1
        j = n - 1
        k = m + n - 1

        while i >= 0 and j >= 0:
            if nums2[j] > nums1[i]:
                nums1[k] = nums2[j]
                j -= 1
            else:
                nums1[k] = nums1[i]
                i -= 1
            k -= 1

        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1

nums1의 원소가 전부 추가되지 않았다면)

그렇다면 nums2는 전부 추가했지만 nums1에 아직 원소가 남아있는 경우도 있을까요?

 

당연합니다.

만약 j가 -1이 되고 i가 0 이상이라면 nums1에 아직 원소가 남아있습니다.

 

하지만 이걸 굳이 다뤄줄 필요가 없습니다.

왜냐하면 이미 올바른 자리에 위치하기 때문이죠.

 

저희는 숫자가 큰 순서부터 오른쪽에서 왼쪽으로 추가했습니다. nums2가 전부 소진 되었다는 것은 nums1에 남아있는 원소들이 nums2의 원소들보다 전부 작다는 뜻이겠죠.

 

고로 이미 올바른 순서로 정렬되어 있는 nums1의 나머지 원소들은 건들일 필요가 없습니다.

디버깅)

nums1 = [2, 3, 5, 0, 0], m=3, nums2 = [1, 4], n=2

 

i = 2

j = 1

k = 4

 

(while i >= 0, j >= 0)

(i = 2, j = 1)

(4 <= 5)

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

i = 1

k = 3

 

(i = 1, j = 1)

(4 > 3)

nums1 = [2, 3, 5, 4, 5]

j = 0

k = 2

 

(i = 1, j = 0)

(1 <= 3)

nums1 = [2, 3, 3, 4, 5]

i = 0

k = 1

 

(i = 0, j = 0)

(1 <= 2)

nums1 = [2, 2, 3, 4, 5]

i = -1

k = 0

 

(while j >= 0)

nums1 = [1, 2, 3, 4, 5]

j = -1

k = -1

 

# output: nums1 = [1, 2, 3, 4, 5]

 

 

처음에는 nums1의 0자리에 작은 숫자들 부터 넣고 자리를 찾을 때까지 스와핑을 해주는 방식을 사용했습니다. submission이 되긴 했지만 문제가 원하는 정답은 아닌 것 같아서 다른 사람들의 정답들을 보니 큰 숫자들을 먼저 넣더군요. 그래서 저도 그런식으로 해봤는데 어떤가요? 잘 설명이 되었으면 좋겠네요 ㅎㅎ.

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)