[Leetcode] 74. Search a 2D Matrix 문제 풀이

https://leetcode.com/problems/search-a-2d-matrix/

Search a 2D Matrix - LeetCode

문제 내용

2차원 배열이 정렬되어 있는 데 

배열에서 target 찾기

Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

 

문제 풀이

binary search 2번 사용해서 풀었다.

row축으로 먼저 upper bound로 찾았다.

upper bound를 찾은 이유는 index-1 하면 해당 값보다 작은 곳을 찾을 수 있기 때문이다.

그리고 lower bound를 찾아서 해결했다.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        vector<int> row(matrix.size());
        for (int y = 0; y < matrix.size(); ++y)
            row[y] = matrix[y][0];
        
        int y = upper_bound(row.begin(), row.end(), target) - row.begin() - 1;
        if (y < 0)
            return false;

        int x = lower_bound(matrix[y].begin(), matrix[y].end(), target) - matrix[y].begin();
        if (x == matrix[y].size())
            return false;

        return matrix[y][x] == target;
    }
};

배열 추가 없이 2차원으로도 풀 수 있다.