[LeetCode | Java | Binary Search 문제 풀이] 1351. Count Negative Numbers in a Sorted Matrix - Solution with Loop

99 Club 2기 | Java | Beginner

📉 1351. Count Negative Numbers in a Sorted Matrix

🏷 관련 주제 : Array Binary Search Matrix Algorithm Complexity

Easy

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.

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

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

Follow up: Could you find an O(n + m) solution?

Accepted    417.2K  |  Submissions    539.4K  |  Acceptance Rate    77.3%

---

✔ Solution with

class Solution {
    public int countNegatives(int[][] grid) {
        int answer = 0;
        int r = grid.length;
        int c = grid[0].length;
        int idx = 0;

        for (int i = r - 1; i >= 0; i--) {
            if (idx == c) {
                break;
            }
            for (int j = idx; j < c; j++) {
                if (grid[i][j] < 0) {
                    answer += (c - j);
                    idx = j;
                    break;
                }
            }
        }
        return answer;
    }
}

채점 결과

---

💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍

📌 오늘 만난 문제 : 매개변수로 m x n 행렬 grid가 주어질 때, grid안의 음수의 개수를 반환하시오.
이 때, grid는 non-increasing order로 정렬되어 있다.
그리고 알고리즘 복잡도 O(n + m)인 풀이를 구하시오.

---

1. 변수 초기화

int answer : 음수의 개수를 담을 변수
int m : grid의 행의 길이를 담은 변수
int n : grid의 열의 길이를 담은 변수
int idx : grid의 각 행에서 이미 양수임이 확정된 인덱스 + 1
행의 각 원소를 탐색할 때, 탐색 시작할 인덱스

int answer = 0;
int m = grid.length;
int n = grid[0].length;
int idx = 0;

2. 반복문으로 grid의 원소 중 음수의 개수가 몇개인지 탐색하자.

행 탐색

grid는 non-increasing order로 정렬되어 있으므로 행렬의 가장 마지막 행부터 탐색

for (int i = m - 1; i >= 0; i--) {
    ...
}

---

열 탐색

• 모든 원소가 양수이면,
  • 그 위의 행도 모두 양수이므로 전체 탐색 종료
  • idx == n이면 전체 반복문을 종료
• 모든 원소가 양수가 아니면,
  • 현재 탐색하는 행의 원소가 양수이면,
    위쪽 행의 같은 위치의 원소도 양수 (위쪽 행 탐색 범위에서 제외)
    • 각 행의 탐색 범위: 아래 행의 원소가 음수인 인덱스들
    • 위쪽 행의 첫 탐색 인덱스(idx)를 아래 행의 첫 음수 원소의 인덱스로 정해주자.
      ⇒ idx = j
  • 현재 탐색하는 행의 원소가 음수이면.
    처음으로 음수가 나오는 인덱스의 다음 원소들도 모두 음수
    (행 탐색 반복문 종료)
    • (현재 행에서 음수의 개수)
      = (grid의 열 길이) - (현재 행 첫 음수 원소의 인덱스)
    • answer에 n - j를 더해주자.

for (int j = idx; j < n; j++) {
    if (grid[i][j] < 0) {
        answer += (n - j);
        idx = j;
        break;
    }
}

💬 무엇을 새롭게 알았는지

문제에서 요구하는 알고리즘 복잡도를 만족시키기 위해 고민하며 문제를 풀어볼 수 있었다.

---

📚 References(참고 자료)

• LeetCode | 내가 작성한 오늘 문제 풀이
• [알고리즘/Python] 시간복잡도(time complexity)