[Leetcode/C++] 240_Search a 2D Matrix II

문제는 다음과 같습니다.

일단, 저는 이 문제를 두 가지 풀이로 풀었구요,

처음 푼 풀이는 다음과 같습니다.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row_count = matrix.size();
        int low_count = matrix[0].size();
        bool res = 0;
        cout<<row_count<<" "<<low_count<<endl;
        
        int l=0, r=0;
        
        while(l<low_count && matrix[0][l]<=target){
            if(matrix[0][l]==target) return true;
            else l++;
        }
        l--;
        
        while(r<row_count && matrix[r][0]<=target){
            if(matrix[r][0]==target) return true;
            else r++;
        }
        r--;
        
        
        int i=1;
        
        while(l>=1 && i<=r){
            
            if(matrix[i][l]==target) return true;
            
            if(i+1<=r && matrix[i+1][l]<=target) i++;
            else l--;
            
        }
        
        return res;
        
    } // searchMatrix 끝
};

먼저 이 풀이의 풀이과정은 두 가지 과정을 거칩니다.

과정 1

• 먼저 matrix[0][l]의 가로줄에서 타겟이하의 최댓값을 찾습니다.
• 이어서 matrix[r][0]의 세로줄에서 타겟이하의 최댓값을 찾습니다.

과정 2

• 여기까지 타겟이 없었다면, matrix[1][l] (l은 과정1에서 구한 값)을 시작으로 타겟을 찾습니다.
  이때, matrix > target이면 왼쪽으로 한 칸 이동하고, matrix < target이면 밑으로 한 칸 이동합니다.

생각을 다시 해 보니, 과정 1을 굳이 거칠 이유가 없더라구요
이 부분 때문에 가로와 세로를 각각의 길이만큼 돌아야하니 시간이 걸린 것 같습니다.
그래서 바로 과정2부터 시작하면 된다고 생각하여
문제 풀이를 바꿨습니다.

그 풀이는 다음과 같습니다.

class Solution {
public:
    bool res = 0;
    
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row_count = matrix.size()-1;
        int low_count = matrix[0].size()-1;
        
        int r = 0;
        int l = low_count;
        
        while(l>=0 && r<=row_count){
            if(matrix[r][l]==target) return true;
            else if(matrix[r][l]<target) r++;
            else l--;
        }
        
        return false;
    } // searchMatrix 끝
};

즉, 첫째줄 제일 오른쪽을 기준으로 시작하여,
아까의 풀이의 과정2를 수행하는 풀이입니다.

다른 분들의 풀이를 찾아보았는데요,
다음과 같습니다.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i = 0;
	    int j = matrix[0].size()-1;
	    while(i<matrix.size() && j>=0){
	        if(matrix[i][j]==target) return true;
	        else if(matrix[i][j]<target)  i++;
	        else  j--;
	    }
	    return false;
    }
};

풀이출처