LeetCode 풀기 - 1351. Count Negative Numbers in a Sorted Matrix

1351. Count Negative Numbers in a Sorted Matrix

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

Count Negative Numbers in a Sorted Matrix - LeetCode

문제)

솔루션1) - brute force

이중 for 문을 통해서 0보다 작은 number를 셉니다.

 

시간 복잡도 : O(m x n)

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        return sum([num < 0 for nums in grid for num in nums])

솔루션2)

오른쪽 상단에서 부터 negative number를 row를 이동시키면서 negative number를 찾습니다.

negative number를 찾으면 최대 row- - 현재 row를 하면 negative number 수가 나옵니다.

여기서 다시 컬럼을 왼쪽으로 이동하면서 이를 반복합니다. 솔루션1 보다는 연산량을 줄일 수 있을 것 같습니다.

그러나 최악의 경우 여전히 시간 복잡도는 O(m x n) 입니다

 

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        # 우측 상단에서 부턴 negative number 수를 센다
        
        max_row = len(grid)
        max_col = len(grid[0])
        
        row = 0
        col = max_col -1
        negative_count = 0
        
        while (row < max_row) and col >= 0:
            if grid[row][col] < 0:
                negative_count += max_row - row
                col -= 1
                
            else:
                row += 1
                
        return negative_count

솔루션3) - binary search 

grid의 각 row에 대해서 바이너리 서치를 적용해서 negative number 수를 찾습니다.

# binary search
class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        max_col = len(grid[0])
        
        def binary_search(arr, low, high):
            while low <= high:
                mid = (low + high) // 2                
                if arr[mid] >= 0:
                    low = mid + 1
                else:
                    high = mid - 1

            return low
        
        # 음수 카운팅 변수
        negative_num_count = 0
        
        # 그리드의 각 row를 순회
        for row in grid:
            # 바이너리 서치 탐색을 이용해서 음수가 시작되는 idx 위치 획득
            start_negative_num_idx = binary_search(row, 0, max_col-1)
            
            negative_num_count += max_col - start_negative_num_idx
            
        return negative_num_count