23.08.07. 풀었던 문제들 복기

Leetcode 74. Search a 2D Matrix, 25분

 matrix가 정렬되어 있으므로 target이 있는 row를 찾고, 이후 col을 찾으면 된다.

 row를 찾을 때 binary search를 하고, col을 찾을 때 binary search를 하면 O(logm + logn)으로 해결할 수 있다.

 

 이외에도, 모범답안은 전체를 하나의 array로 보고, index / m을 row index, index / n을 col index로 보고 O(log(m*n))만에 해결하는 방법도 있다.

// Runtime 3 ms Beats 82.89%
// Memory 9.6 MB Beats 19.73%

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();

        // lower bound로 찾는 식으로 -> matrix[i][0]으로 찾으면 upper bound로 찾고 -1 해야 한다. 귀찮다!
        // 따라서 matrix[i][n-1]로 찾는다. target이 들어 있을 만한 행을 찾기 위해서이다.
        int start = 0, end = m, mid;
        while(start < end){
            mid = (start + end)/2;
            if(matrix[mid][n-1] >= target) end = mid; // 앞으로 당겨야 함
            else start = mid + 1;
        }
        if(end == m || (end == 0 && matrix[0][0] > target)) return false;
        int i = start;
        
        // col 찾기
        start = 0; end = n;
        while(start < end){
            mid = (start + end)/2;
            if(matrix[i][mid] >= target) end = mid; // 앞으로 당겨야 함
            else start = mid + 1;
        }
        if(end == n || matrix[i][end] != target) return false;

        return true;
    }

};

/*
binary search 2번?
*/

 

시간복잡도

 row size를 m, col size를 n이라 하면  O(logm + logn)