99클럽 코테 스터디 17일차 TIL Count Negative Numbers in a Sorted Matrix

Count Negative Numbers in a Sorted Matrix

• 문제 풀이

  1. 이중 for문에 대해서 0보다 작을때 cnt++하여 최종적으로 cnt를 return하는 문제

• 풀이 소스

class Solution {
    public int countNegatives(int[][] grid) {
        int cnt = 0;
        for(int i=0; i< grid.length; i++){
            for(int j=0; j< grid[i].length; j++){
                if(grid[i][j]< 0){
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

• 다른 풀이

class Solution {
    public int countNegatives(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int row = 0;
        int col = 0;
        int cnt = 0;
        while(rows>row && cols>col){
           if(grid[row][col] >=0){
               col++;
           }else{
               cnt += cols-col;
               row++;
               col=0;
           }
           if(cols == col){
              col=0;
              row++;
           }
           
        }
        return cnt;
    }
}

• 오늘의 회고

  • 문제 시도 및 해결

    • 처음에 단순히 이중 for문으로 문제를 해결했다.
    • 이진탐색을 사용하라는 힌트를 얻어서 다른 방식으로 문제를 풀려고 했다.
    • 주어진 배열을 나열하면 다음과 같이 나온다.
    • 이제 첫번째 행과 첫번째 열부터 체크하며 값을 비교하며 0보다 작지 않은때 열을 1씩 더해가면서 비교했다.
    • 그렇게 비교하다가 0보다 작은값이 나온 인덱스는 열의 전체길이에서 index를 뺸값이 cnt로 더해지는 방식이다.
    • 그러고 col이 cols와 같아지면 row++를 더하주고 col은 0으로 다시 선언하여 위와 같은 방식을 수행한다.
    • 그 후 row와 col이 각각 rows와 cols보다 크거나 같게되면 while문을 종료한다.

• 학습 내용 및 회고

  • 이분탐색과 완전탐색을 사용하라는 힌트를 듣고 문제를 풀 수 있었다.

• 다음 배울것

  • 코테 문제 풀이
  • 이분탐색과 완전탐색