Count Negative Numbers in a Sorted Matrix

문제설명

주어진 m \times n 행렬(grid)은 행과 열 모두 내림차순으로 정렬되어 있습니다. 이 행렬에서 음수의 개수를 반환하세요.

예제 1:

•	입력: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
•	출력: 8
•	설명: 이 행렬에는 8개의 음수가 있습니다.

예제 2:

•	입력: grid = [[3,2],[1,0]]
•	출력: 0
•	설명: 이 행렬에는 음수가 없습니다.

제약 조건:

•	m == grid.length
•	n == grid[i].length
•	1 <= m, n <= 100
•	-100 <= grid[i][j] <= 100

추가 과제:

O(n + m) 시간 복잡도로 해결할 수 있습니까?

문제풀이

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        count = 0

        row = 0
        col = n - 1
        
        while row < m and col >= 0:
            if grid[row][col] < 0:
                count += (m - row)
                col -= 1
            else:
                row += 1
        
        return count

<내 코드의 흐름>

1. countNegatives라는 메서드를 정의합니다.

• 이 메서드는 grid라는 2차원 리스트(행렬)를 인자로 받아 음수의 개수를 세고, 정수형으로 반환합니다.

2. m 변수에 행렬의 행(row) 수를 저장합니다.

• len(grid)는 행렬의 행 수를 반환합니다.

3. n 변수에 행렬의 열(column) 수를 저장합니다.

• len(grid[0])는 행렬의 첫 번째 행의 열 수를 반환합니다.

4. count 변수를 0으로 초기화합니다.

• 이 변수는 음수의 개수를 세는 데 사용됩니다.

5. row 변수를 0으로 초기화합니다.

• 탐색을 시작할 행의 인덱스를 나타냅니다.

6. col 변수를 n - 1로 초기화합니다.

• 탐색을 시작할 열의 인덱스를 나타내며, 이는 오른쪽 상단에서 시작하기 위해 설정됩니다.

7. while 루프를 시작합니다. row가 m보다 작고 col이 0보다 크거나 같은 동안 반복됩니다.

• 이 조건은 행렬을 벗어나지 않도록 보장합니다.

8. 현재 위치의 값이 음수인지 확인합니다.

• grid[row][col]이 0보다 작은지 확인합니다.

9. 현재 위치의 값이 음수이면, 해당 열 아래의 모든 값도 음수이므로, 남아 있는 모든 행의 개수를 count에 더합니다.

• m - row는 현재 행부터 마지막 행까지의 개수를 나타냅니다.

10. 음수를 찾은 경우, 왼쪽 열로 이동하기 위해 col 값을 1 감소시킵니다.
11. 현재 위치의 값이 0 이상인 경우를 처리하기 위한 else 블록입니다.
12. 현재 위치의 값이 0 이상이면, 아래 행으로 이동하기 위해 row 값을 1 증가시킵니다.
13. count 값을 반환합니다.

• 이는 행렬에서 발견된 모든 음수의 개수를 나타냅니다.