1. 문제

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

증가하지 않는 순서로 정렬된 m * n 행렬이 주어질 때, 행렬 안의 음수 개수를 반환하라

2. 내 풀이

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        ans = 0
        m = len(grid)
        n = len(grid[0])
        
        for i in range(m):
            if i < 0:
                ans += (m - i) * n
                break
            for j in range(n):
                if grid[i][j] < 0:
                    ans += (n - j)
                    break
        
        return ans

배열을 모두 돌며 음수를 만날 때마다 ans 변수를 업데이트 해 준다

3. 다른 풀이

Binary Search를 사용한 풀이...

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        count = 0
        n = len(grid[0])
        # Iterate on all rows of the matrix one by one.
        for row in grid:
            # Using binary search find the index
            # which has the first negative element.
            left, right = 0, n - 1
            while left <= right:
                mid = (right + left) // 2
                if row[mid] < 0:
                    right = mid - 1
                else:
                    left = mid + 1
            # 'left' points to the first negative element,
            # which means 'n - left' is the number of all negative elements.
            count += (n - left)
        return count

4. 느낀점

binary search를 떠올리지 못했다!!!!!! 담엔 꼭 고려해 보기