Merge Two 2D Arrays by Summing Values

EasyArrayHash TableTwo Pointers

문제 설명

두 개의 정수 배열 nums1과 nums2가 주어진다.

각 배열의 요소는 [id, value]의 형식이며 다음 규칙을 따른다.

id는 고유한 숫자로, 오름차순으로 정렬되어 있다.
같은 id를 가진 요소가 두 배열에 존재할 수 있다.

주어진 두 개의 정수 배열을 다음과 같은 규칙으로 병합하여 반환해야한다.

id가 하나라도 등장하는 경우, 결과 배열에 포함해야 한다.
같은 id가 존재하면 값을 합산하여 포함해야 한다.
최종 결과 배열도 오름차순 정렬된 상태여야 한다.

문제 풀이

`Hash Table`

Map을 사용하여, id를 키 값으로 저장하고, 값을 합산하여 업데이트한 후, 다시 정렬하여 반환한다.

function mergeArrays(nums1: number[][], nums2: number[][]): number[][] {
  const values = new Map<number, number>();
  for (const [id, value] of nums1) {
    values.set(id, value);
  }
  for (const [id, value] of nums2) {
    values.set(id, (values.get(id) ?? 0) + value);
  }
  return [...values].sort(([a], [b]) => a - b);
}

복잡도

시간 복잡도: $O((m + n) \cdot log_2{(m + n)})$
공간 복잡도: $O(m + n)$

`Two Pointers`

두 배열이 이미 정렬된 상태이므로 두 개의 포인터를 사용하여 병합할 수 있다.

nums1[i][0]와 nums2[j][0] 값을 비교한다.
- 값이 같은 경우, nums1[i][1] + nums2[j][1]을 결과에 추가하고, 두 포인터 모두 증가시킨다.
- 값이 다른 경우, 작은 id를 가진 요소를 그대로 결과에 추가하고, 해당 포인터를 증가시킨다.
남은 요소가 있다면 결과 배열에 추가한다.

function mergeArrays(nums1: number[][], nums2: number[][]): number[][] {
  const answer: number[][] = [];
  const [m, n] = [nums1.length, nums2.length];
 
  let [i, j] = [0, 0];
  while (i < m && j < n) {
    if (nums1[i][0] < nums2[j][0]) {
      answer.push(nums1[i]);
      i += 1;
    } else if (nums1[i][0] > nums2[j][0]) {
      answer.push(nums2[j]);
      j += 1;
    } else {
      answer.push([nums1[i][0], nums1[i][1] + nums2[j][1]]);
      i += 1;
      j += 1;
    }
  }
  while (i < m) {
    answer.push(nums1[i]);
    i += 1;
  }
  while (j < n) {
    answer.push(nums2[j]);
    j += 1;
  }
  return answer;
}

복잡도

시간 복잡도: $O(m + n)$
공간 복잡도: $O(m + n)$

LeetCode

Merge Two 2D Arrays by Summing Values

https://leetcode.com/problems/merge-two-2d-arrays-by-summing-values