[leetCode/JS] 1351. Count Negative Numbers in a Sorted Matrix

난이도 [ 😊 ] 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.

여기서 non-increasing order는 내림차순(값이 같거나 작아짐)을 의미함.
그리고 이게 row-wise(가로)와 column-wise 모두에 적용된다는 것이 핵심.

입출력 예

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0

Constraints

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

Follow up: Could you find an O(n + m) solution?

---

내 솔루션

/**
 * @param {number[][]} grid
 * @return {number}
 */
var countNegatives = function(grid) {
    let row = grid.length - 1; // --
    let col = 0; // ++

    const n = grid[0].length;

    let count = 0;

    while(row >= 0 && col < n){
        if(grid[row][col] < 0) {
            count += (n - col)
            row--;
        } else {
            col++;
        }
    }
    return count;
};


// [[4,3,2,-1],
//  [3,2,1,-1],
//  [1,1,-1,-2],
//  [-1,-1,-2,-3]]

감상평

• 2차원 m * n 에서 n만 내림 차순인줄 알고 바이너리 서치를 통해 해결하려다가
• O(n+m)이 가능하다 Follow up 힌트에서 가로 세로 모두 정렬 되어 있구나! 를 알아 차림.
• 영문을 너무 띄엄 띄엄 읽는게 문제야