[99클럽] 코테 스터디 22일차 TIL - 이분탐색(1351. Count Negative Numbers in a Sorted Matrix)

문제

문제 설명

행, 열 모두 내림차순으로 정렬된 2차원 배열이 주어진다.
배열에서 음수의 개수를 반환하라.

예시

• 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제약 조건
• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

풀이 방법

풀이 로직

• 이분탐색 알고리즘 이용

1. 각 행에서 이분 탐색 알고리즘을 이용하여 음수를 찾는다.
2. 음수를 찾았다면 mid ~ 오른쪽 부분을 모두 음수로 처리하고 왼쪽 부분을 이분 탐색한다.
3. 1, 2번 과정을 반복하다 행의 끝부분까지 모두 탐색했다면 다음 행으로 넘어간다.

코드

• 반복문 방식

/** 반복문
 - 각 행을 탐색(for(grid.length))하고 각 행의 끝부분까지만 탐색(while(start > end))한다. */

class Solution {
    public int countNegatives(int[][] grid) {
        int result = 0;

        for (int i = 0; i < grid.length; i++) {
            int start = 0; 
            int end = grid[i].length-1; // 4

            // 행의 끝부분 까지만 탐색
            while (start <= end) {
                int mid = (start + end) / 2;

                // mid가 음수인 경우 -> mid~오른쪽 부분 음수로 처리 && 왼쪽 부분 이분탐색
                if (grid[i][mid] < 0) { 
                    result += end - mid + 1;
                    end = mid-1;
                }

                // mid == 양수 or 0 -> 오른쪽 부분 이분탐색
                else
                    start = mid + 1;
            }
        }
        return result;
    }
}

오늘 회고

엄청 쉬운 문제인데도 조금 헤멨다.
이런 쉬운 문제를 바로 풀지 못했다는 게 너무 아쉽다.
그래도 풀었으면 된거지