99클럽 코테 스터디 22일차 TIL + 이진탐색 Binary Search, [leetcode] Count Negative Numbers in a Sorted Matrix

✨ 문제 

Count Negative Numbers in a Sorted Matrix 

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity. 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.

 

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

 

 

 

✨ 개념

이진탐색 Binary Search

- 정렬된 배열에서  특정 값을 찾는 알고리즘.

- 검색 범위를 절반씩 줄여가며 원하는 값을 찾음.

- 시간복잡도가 O(log n)으로 매우 빠름

 

 

✨ 최종코드

class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        int row = 0;
        int col = n - 1;
        
        while (row < m && col >= 0) {
            if (grid[row][col] < 0) {
                count += (m - row); // 현재 열에 있는 모든 행(row 포함)에 음수 존재
                col--; // 왼쪽 열로 이동
            } else {
                row++; // 다음 행으로 이동
            }
        }
        
        return count;
    }
}