leetcode - Count Negative Numbers in a Sorted Matrix

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

Count Negative Numbers in a Sorted Matrix - LeetCode

 

완전 탐색으로 풀면 더 쉽게 풀겠지만, 문제 분류가 이진 탐색이기 때문에 이진 탐색 방식으로 풀었다.

각각의 1차원 배열에 음수의 총 갯수를 구하는 문제이다!

 

public int countNegatives(int[][] grid) {
	int count = 0;
		
	for (int[] arr : grid) {
		int idx = negativeNumIdx(arr);
		count += (arr.length - idx);
	}
	return count;
}
	
private int negativeNumIdx(int[] arr) {
	int high = arr.length - 1;
	int low = 0;
		
	while (low <= high) {
		int mid = (low + high) / 2;
		if (arr[mid] < 0) {
			while (mid != -1 && arr[mid] < 0) {
				mid--;
			}
			return mid + 1;
		}
		low = mid + 1;
	}
	return arr.length;
}

 

 

1차원 배열 요소들은 내림차순 되어있다.

반복문을 통해 배열의 맨 앞에 있는 음수의 idx를 구해서, 배열의 길이만큼 빼면 요소 당 음수의 갯수를 구할 수 있다.