문제 설명

Merge Sorted Array - LeetCode

해설

문제의 핵심 요구사항:

  • 정렬된 두 배열 nums1과 nums2를 병합해야 합니다.
  • nums1 배열의 길이는 m + n이며, 처음 m개의 요소만 유효한 값이고 나머지는 0으로 채워져 있습니다.
  • 결과는 새로운 배열을 반환하는 것이 아니라 nums1 배열 자체를 수정해야 합니다.
  • 최종 결과는 오름차순으로 정렬되어야 합니다.

이 문제를 해결하기 위한 가장 효율적인 접근 방법은 뒤에서부터 배열을 채워나가는 것입니다. 그 이유는:

  1. nums1의 뒷부분은 0으로 채워져 있어서 덮어쓸 수 있습니다.
  2. 두 배열이 이미 정렬되어 있으므로, 각 배열의 가장 큰 값부터 비교하여 더 큰 값을 nums1의 뒤에서부터 채워넣을 수 있습니다.
  3. 이 방식을 사용하면 추가적인 공간이 필요하지 않습니다.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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

Step 1: 마지막 위치(5)부터 시작
비교: 3 vs 6 → 6이 더 큼
nums1 = [1,2,3,0,0,6]

Step 2: 다음 위치(4)
비교: 3 vs 5 → 5가 더 큼
nums1 = [1,2,3,0,5,6]

Step 3: 다음 위치(3)
비교: 3 vs 2 → 3이 더 큼
nums1 = [1,2,3,3,5,6]

Step 4: 다음 위치(2)
비교: 2 vs 2 → 같음
nums1 = [1,2,2,3,5,6]

…계속

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # 포인터 초기화: p1은 nums1의 마지막 실제 요소, p2는 nums2의 마지막 요소
        p1 = m - 1
        p2 = n - 1
        # p는 nums1의 마지막 위치
        p = m + n - 1
        
        # 뒤에서부터 큰 값을 채워넣기
        while p2 >= 0:  # nums2의 모든 요소를 처리할 때까지
            # nums1의 현재 요소가 더 크고, 아직 처리할 요소가 남아있다면
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            # nums2의 현재 요소가 더 크거나, nums1의 처리할 요소가 없다면
            else:
                nums1[p] = nums2[p2]
                p2 -= 1
            p -= 1

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
function merge(nums1, m, nums2, n) {
    // 각 배열의 마지막 요소부터 시작하는 포인터 설정
    let p1 = m - 1;  // nums1의 실제 마지막 요소 위치
    let p2 = n - 1;  // nums2의 마지막 요소 위치
    let p = m + n - 1;  // nums1의 마지막 위치
    
    // nums2의 모든 요소가 처리될 때까지 반복
    while (p2 >= 0) {
        // nums1의 현재 요소가 더 크고, 아직 처리할 요소가 남아있다면
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } 
        // nums2의 현재 요소가 더 크거나, nums1의 처리할 요소가 없다면
        else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
}

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform