LeetCode [2965]: Find Missing and Repeated Values

📌 LeetCode [2965]: Find Missing and Repeated Values

---

문제 설명 📄

2D 리스트 grid가 주어졌을 때:

1. 반복되는 값(하나 이상의 빈도)과
2. 누락된 값(주어진 값의 범위에서 누락된 값)을 구합니다.

결과는 [반복된 값 리스트] + [누락된 값 리스트] 형태로 반환합니다.

---

문제 해결 접근 📋

1. 패턴 생성:
   • 각 값의 빈도를 저장하기 위해 딕셔너리 pattern을 사용합니다.
   • grid의 모든 요소를 순회하며 빈도를 계산합니다.
   • 총 길이 length를 계산하여 범위를 확인합니다.
2. 결과 계산:
   • 1부터 length까지의 범위를 순회하며:
     • pattern에 없는 값은 누락된 값(missing)으로 추가합니다.
     • 빈도가 1보다 큰 값은 반복된 값(repeat)으로 추가합니다.
3. 최종적으로 repeat + missing을 반환합니다.

---

Solution 💻

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        pattern = {}
        length = 0

        for arr in grid:
            for num in arr:
                if num not in pattern:
                    pattern[num] = 0
                pattern[num] += 1
                length += 1

        repeat = []
        missing = []
        for i in range(1, length + 1):
            if i not in pattern:
                missing.append(i)
            elif pattern[i] > 1:
                repeat.append(i)

        return repeat + missing

시간 복잡도 ⏲️

• 시간 복잡도: O(n)
  • n은 grid의 전체 요소 개수입니다.
  • 요소 순회 및 범위 확인에 O(n).

공간 복잡도 🗄️

• 공간 복잡도: O(n)
  • pattern 딕셔너리를 사용해 값의 빈도를 저장.

---

리팩토링 🛠️

개선된 코드

from itertools import chain

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        pattern = {}
        flat_grid = chain.from_iterable(grid)
        repeat = []
        missing = []

        length = 0
        for num in flat_grid:
            if num in pattern:
                pattern[num] += 1
            else:
                pattern[num] = 1
            length += 1

        for i in range(1, length + 1):
            if i not in pattern:
                missing.append(i)
            elif pattern[i] > 1:
                repeat.append(i)

        return repeat + missing

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

• 시간 복잡도: O(n)
  • 모든 요소를 한 번만 순회.

리팩토링 후 공간 복잡도 🗄️

• 공간 복잡도: O(n)
  • 동일하게 pattern 딕셔너리를 사용.

---