LeetCode [73]: Set Matrix Zeroes

📌 LeetCode [73]: Set Matrix Zeroes

🔗 문제 링크

---

문제 설명 📄

2D 행렬 matrix가 주어졌을 때, 요소가 0인 위치의 행과 열 전체를 0으로 바꾸는 문제입니다.
행렬을 제자리에서(in-place) 수정해야 하며, 추가적인 공간 사용을 최소화해야 합니다.

---

문제 접근 방식 📋

1. 0 위치 기록:
   • 2중 루프를 통해 행렬을 순회하며, 값이 0인 좌표를 기록합니다.
   • 좌표는 stack에 저장하여 나중에 접근합니다.
2. 0 확장:
   • 기록된 좌표를 기준으로, 해당 좌표의 행과 열 전체를 0으로 설정합니다.
   • 각 방향(왼쪽, 오른쪽, 위, 아래)을 개별적으로 처리하며, 경계 조건을 확인합니다.
3. 제자리 수정:
   • 행렬을 직접 수정하여 공간 복잡도를 최소화합니다.

---

Solution 💻

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        stack = []

        rows = len(matrix)
        cols = len(matrix[0])

        # 0의 위치를 기록
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == 0:
                    stack.append((i, j))

        # 기록된 좌표를 기준으로 행과 열을 0으로 설정
        for x, y in stack:
            left = [x, y - 1]
            right = [x, y + 1]
            up = [x - 1, y]
            down = [x + 1, y]
            while left[1] >= 0 or right[1] < cols or up[0] >= 0 or down[0] < rows:
                if left[1] >= 0:
                    matrix[left[0]][left[1]] = 0
                    left[1] -= 1
                if right[1] < cols:
                    matrix[right[0]][right[1]] = 0
                    right[1] += 1
                if up[0] >= 0:
                    matrix[up[0]][up[1]] = 0
                    up[0] -= 1
                if down[0] < rows:
                    matrix[down[0]][down[1]] = 0
                    down[0] += 1

---

시간 복잡도 분석 ⏲️

• 시간 복잡도:
  • 첫 번째 루프: 행렬의 모든 요소를 순회하여 0을 찾으므로 O(m * n).
  • 두 번째 루프(0 확장): 각 0에 대해 최대 O(m + n) 작업.
  • 최악의 경우, O((m + n) * k), 여기서 k는 행렬에 있는 0의 개수입니다.
• 공간 복잡도: O(k).
  • k는 0의 좌표를 저장하는 stack의 크기입니다.

---

리팩토링 🛠️

개선된 코드 (최소 공간 사용)

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rows, cols = len(matrix), len(matrix[0])
        first_row, first_col = False, False

        # 첫 번째 행과 열에 0이 있는지 확인
        for i in range(rows):
            if matrix[i][0] == 0:
                first_col = True
        for j in range(cols):
            if matrix[0][j] == 0:
                first_row = True

        # 첫 번째 행과 열을 사용해 0 위치를 표시
        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        # 표시된 위치에 따라 행과 열을 0으로 설정
        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        # 첫 번째 행과 열 처리
        if first_row:
            for j in range(cols):
                matrix[0][j] = 0
        if first_col:
            for i in range(rows):
                matrix[i][0] = 0

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

• 시간 복잡도: O(m * n).
  • 한 번의 순회로 0을 찾고, 다시 순회하며 값을 수정합니다.
• 공간 복잡도: O(1).
  • 추가 메모리 없이, 첫 번째 행과 열을 상태 저장에 활용합니다.

---