[LeetCode] 1351. Count Negative Numbers in a Sorted Matrix

https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/description/

Count Negative Numbers in a Sorted Matrix - LeetCode

문제 유형 : 이진탐색

문제 난이도 : Easy

 

문제

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차원배열에서 음수의 개수를 구하여라.

 

 

풀이

이진탐색을 이용하여 빠른 속도로 풀 수 있다.

mid가 양수이면 인덱스를 늘리면 되고, 음수이면 줄이면 된다.

 

코드(C++)

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int count = 0;
        const int m = grid.size();
        const int n = grid[0].size();

        for(int i = 0; i < m; i++){
            if(grid[i][n-1] >= 0) continue;
            int mid = 0;
            int left = 0;
            int right = n - 1;

            while(left <= right){
                int mid = left + (right - left) / 2;

                if(grid[i][mid] < 0){
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            count += n - left;
        }

        return count;
    }
};