Merge Sorted Arrays Explanation

Problem Summary

Write a function that merges two sorted arrays into one sorted array.

Detailed Explanation

이 문제는 **투 포인터(Two Pointer)** 기법을 사용한 병합 알고리즘을 학습합니다. 병합 정렬의 핵심 연산입니다. **투 포인터 접근법** 각 배열에 포인터(인덱스)를 하나씩 두고, 더 작은 값을 가진 쪽에서 요소를 가져옵니다. **알고리즘 동작** 1. i=0 (arr1 포인터), j=0 (arr2 포인터) 2. arr1[i]와 arr2[j] 비교 3. 더 작은 값을 result에 추가하고 해당 포인터 증가 4. 한 배열이 끝날 때까지 반복 5. 남은 요소들 추가 **[1,3,5]와 [2,4,6] 병합 과정** - 1 < 2 → result=[1], i=1 - 3 > 2 → result=[1,2], j=1 - 3 < 4 → result=[1,2,3], i=2 - 5 > 4 → result=[1,2,3,4], j=2 - 5 < 6 → result=[1,2,3,4,5], i=3 - arr1 끝 → arr2 나머지 추가: [1,2,3,4,5,6] **남은 요소 처리** `result.concat(arr1.slice(i), arr2.slice(j))` - 한 배열이 먼저 끝나면 다른 배열의 남은 요소를 모두 추가 - 이미 정렬되어 있으므로 그대로 붙이면 됨 **왜 O(n+m)인가?** 각 요소를 정확히 한 번씩만 처리하므로 선형 시간입니다.

Solution Code

solution.js

function mergeSorted(arr1, arr2) {
  const result = [];
  let i = 0, j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) result.push(arr1[i++]);
    else result.push(arr2[j++]);
  }
  return result.concat(arr1.slice(i), arr2.slice(j));
}

Key Concepts from This Problem

1. 투 포인터 기법

2. 병합 알고리즘

3. 정렬된 배열

4. 병합 정렬의 기초

Common Mistakes

✗ while 조건에서 && 대신 ||를 사용하면 배열 범위를 벗어납니다

✗ 한 배열이 끝난 후 남은 요소를 추가하는 것을 잊으면 안 됩니다

✗ i++와 ++i의 차이를 이해해야 합니다

Hints

Hint 1: 두 포인터를 사용하세요.

Hint 2: 더 작은 값을 결과에 추가하세요.

Complexity Analysis

Time Complexity

O(n + m)

Space Complexity

O(n + m)

Related Tags

#알고리즘 #정렬 #투포인터