[항해99]99클럽 코테 스터디 15일차 TIL + 이분탐색

 

 

1.  오늘의 학습 키워드 : 이분 탐색(Binary Search)

오늘의 문제는 정렬된 2차원 배열에서 음수의 개수를 찾는 문제였습니다.

2.  오늘의 문제 :  Count Negative Numbers In a sorted matrix

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

클럽장님께서 오늘은 완전탐색과 이진탐색을 같이 혼합해 풀라고 하셨는데 저는 그 말에 더 헷갈려서 시간을 쓴 것 같네요... 근데 혼합하는게 맞았어요!

3.  풀이 

class Solution {
    public int countNegatives(int[][] grid) {
       int n = 0;
        for(int i=0; i< grid.length; i++){
            int left = 0, right = grid[i].length - 1; 
            while(left<=right){
                int mid = (left + right) / 2;
                if(grid[i][mid] >= 0)
                    left = mid + 1;
                else
                    right = mid - 1;
               
        }
            
            n += (grid[i].length-1) - right;
            
    }
        return n;        
    }
}

 

리트코드 discuss를 엄청 찾아가며.. O(n+m)은 어떻게 하는ㄴ건지 찾아보았습니다....ㅋㅋ ㅜㅜ

너무 어렵네요 정말... 이렇게 easy문제도 못푸나 풀면서 현타가 너무 왔어요..

3.  회고 

처음에 계속 오류가 나서 왜그런가.. 했는데 n*m배열인걸 간과한거였습니다. 예시에 다 n*n만 나와서 그거만 가지고 grid.length라고 했는데 grid[i]를 꼭 붙어야했어요!!!! 지피티에게 물어봤었는데 참...잘알려주더군요