LeetCode [2570]: Merge Two 2D Arrays by Summing Values

📌 LeetCode [2570]: Merge Two 2D Arrays by Summing Values

🔗 문제 링크

---

문제 설명 📄

두 개의 2D 배열 nums1과 nums2가 주어졌습니다.
각 배열은 [id, value]의 쌍으로 이루어져 있으며, 정렬된 상태입니다.
동일한 id 값을 가진 value를 더한 후, 결과를 [id, sum]의 형태로 정렬된 배열로 반환해야 합니다.

---

문제 접근 방식 📋

1. 딕셔너리를 이용한 병합:
   • 두 배열의 모든 요소를 순회하며, 각 id를 키로 저장하고 value를 더합니다.
   • Python의 defaultdict를 활용하여 초기화 과정을 간소화합니다.
2. 결과 생성:
   • 딕셔너리의 키를 기준으로 정렬한 후, [id, sum]의 형태로 배열을 생성합니다.
3. 시간 최적화:
   • 두 배열을 합친 후 병합하는 방식으로 (O(m + n + k \log k)) 시간 복잡도를 유지합니다.

---

Solution 💻

from collections import defaultdict

class Solution:
    def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
        pattern = defaultdict(int)

        for id, value in nums1 + nums2:
            pattern[id] += value

        return [[id, value] for id, value in sorted(pattern.items())]

---

시간 복잡도 분석 ⏲️

• 시간 복잡도:
  • 두 배열을 순회: (O(m + n)), (m)은 nums1의 길이, (n)은 nums2의 길이.
  • 딕셔너리를 정렬: (O(k \log k)), (k)는 고유한 id의 개수.
  • 최종적으로 (O(m + n + k \log k)).
• 공간 복잡도:
  • 딕셔너리 pattern: (O(k)), 고유 id의 개수.

---

리팩토링 🛠️

개선된 코드 (병합 정렬)

class Solution:
    def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
        answer = []
        i, j = 0, 0
        m, n = len(nums1), len(nums2)

        while i < m and j < n:
            if nums1[i][0] == nums2[j][0]:  
                answer.append([nums1[i][0], nums1[i][1] + nums2[j][1]])
                i += 1
                j += 1
            elif nums1[i][0] < nums2[j][0]: 
                answer.append(nums1[i])
                i += 1
            else: 
                answer.append(nums2[j])
                j += 1

        while i < m:
            answer.append(nums1[i])
            i += 1
        while j < n:
            answer.append(nums2[j])
            j += 1

        return answer

리팩토링 후 시간 복잡도 ⏲️

• 시간 복잡도:
  • 두 배열 병합: O(m+n)O(m + n).
  • 추가적인 정렬이 필요 없으므로 O(klog⁡k)O(k \log k) 제거.
• 공간 복잡도:
  • 결과 배열 answer: O(m+n)O(m + n).

---