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

문제(원문)

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.

 

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

 

Example 3:

Input: grid = [[1,-1],[-1,-1]] Output: 3

 

Example 4:

Input: grid = [[-1]] Output: 1

 

Constraints:

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

 

문제(해석)

2차원 배열에서 음수의 갯수를 반환하라.

 

나의 풀이

사실 가장 먼저 떠오른 방법은 배열의 모든 요소를 for문 돌며 값비교였지만...

뭔가 비효율적인것 같아 이진검색을 이용했다.

우선 각 1차원배열을 sort(정렬)하여 순서대로 오게 만든다.

이후 이진검색을 이용해 0의 위치를 찾는다. 

0보다 왼쪽에 있는 요소는 음수이므로, 0의 위치가 음수의 갯수가 된다.

(여기서 0이 중복되어 있는 경우 맨 앞의 0 위치를 찾아야 한다. 중복된 배열의 검색은 아래 더 자세히 설명하도록 하겠다.)

이 방식으로 1차원배열을 모두 돌며 음수의값을 누적한다.

 

Runtime: 1 ms

Memory Usage: 39.4 MB

 

class Solution {
    public static int countNegatives(int[][] grid) {
  
        int count = 0;
        int key = 0;
        
        for(int i = 0; i<grid.length; i++){
            
            int start = 0;
            int end = grid[i].length - 1;
            int half = 0;
            
            Arrays.sort(grid[i]);
            
            do{
                half = (start + end) / 2;

                if(grid[i][half] < key){ 
                    start = half + 1;
                }else{
                    end = half - 1;
                }

            }while(start <= end);

            count = count + start; 
        }       
    return count;
    }
}