1. 오늘의 문제

Count Negative Numbers in a Sorted Matrix

• 출처 : leetcode

2. 문제 분석

• grid : m * n 크기의 2차원 배열
• grid는 행, 렬 모두 내림 차순으로 정렬되어 있음
• 리턴 값 : 음수의 개수
• m : grid.length
• n : grid[i].length
• 1 $\leq$ m, n $\leq$ 100
• -100 $\leq$ grid[i][j] $\leq$ 100

• 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

3. 문제 풀이

1. 이진 탐색을 통해 문제 풀이
2. 음수 담을 변수 count 생성
3. for 문을 이용해 행마다 이진 탐색 실시
4. 투 포인터를 사용해 left, right 생성해 각각 0, grid[i].length - 1 대입
5. left가 right보다 항상 작거나 같다고 가정하고 반복
6. 이진 탐색을 통해 mid 를 left + (right - left) / 2 로 생성
7. 만약 mid의 값이 0보다 작으면(음수이면) right를 mid-1로 설정 후 반복
8. 만약 mid가 음수가 아니면 left를 mid+1로 설정 후 반복
9. 이렇게 되면 결국 left는 첫 번째 음수의 인덱스가 들어가게 됨. 만약 음수가 없으면 left는 m의 크기가 됨. 즉, 음수의 개수는 m - left가 된다. 이 값을 count에 더해주면 됨.
10. count 리턴

4. 구현 코드

class Solution {
    public int countNegatives(int[][] grid) {
        // 이진 탐색을 통해 문제 풀이

        // 음수 담을 변수 count 생성
        int count = 0;

        // for 문을 이용해 행마다 이진 탐색 실시
        for (int[] row : grid) {
            // 투 포인터를 사용해 left, right 생성해 각각 0, grid[i].length - 1 대입
            int left = 0, right = row.length - 1;

            // left가 right보다 항상 작거나 같다고 가정하고 반복
            while (left <= right) {
                // 이진 탐색을 통해 mid 를 left + (right - left) / 2 로 생성
                int mid = left + (right - left) / 2;
                // 만약 mid값이 0보다 작으면(음수이면) right를 mid-1로 설정 후 반복
                if (row[mid] <0) {
                    right = mid - 1;
                // 만약 mid가 음수가 아니면 left를 mid+1로 설정 후 반복
                } else {
                    left = mid + 1;
                }
            }
            // 이렇게 되면 결국 left는 첫 번째 음수의 인덱스가 들어가게 됨.
            // 만약 음수가 없으면 left는 m의 크기가 됨.
            // 즉, 음수의 개수는 m - left가 된다. 이 값을 count에 더해주면 됨.
            count += row.length - left;
        }
        // count 리턴
        return count;
    }
}

5. 오늘의 회고

• 이진 탐색에 대해 배울 수 있었다.
• 이진 탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘이다.

이진 탐색의 원리

1. 배열의 가운데 요소 선택
2. 선택한 요소가 찾고자 하는 값과 같다면 탐색 종료
3. 찾고자 하는 값이 선택한 요소보다 작다면, 배열의 왼쪽 절반을 대상으로 이진 탐색 수행
4. 찾고자 하는 값이 선택한 요소보다 크다면, 배열의 오른쪽 절반을 대상으로 이진 탐색 수행

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL