[C++] LeetCode : Search a 2D Matrix II

Question

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

 

m x n 정수 행렬 행렬에서 값 대상을 찾는 효율적인 알고리즘을 작성하십시오. 이 행렬에는 다음과 같은 속성이 있습니다.

각 행의 정수는 왼쪽에서 오른쪽으로 오름차순으로 정렬됩니다.
각 열의 정수는 위에서 아래로 오름차순으로 정렬됩니다.

 

제약사항

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matrix[i][j] <= 10^9
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• -10^9 <= target <= 10^9

---

 

Solution1 (Bruth Force)

2차원 배열에서 숫자를 찾는 효율적인 방법을 찾는 문제이다. 
생각할 수 있는 가장 단순한 방법은 모든 배열을 loop를 돌면서 원소를 찾는 방식이다. 

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

• Time complexity : O(mn) 
• Space Complexity : O(1) 

Solution2

Solution1의 방법은 행과 열이 오름차순으로 정렬되어있다는 특징을 전혀 활용하지 않은 방법이다. 
오름차순 정렬되어있다는 사실을 활용한다면, 맨 오른쪽 위 꼭짓점 또는 맨 왼쪽 아래 꼭짓점을 기준으로 정답을 찾아갈 수 있다. 
맨 오른쪽 위 꼭짓점을 기준으로 한다면 해당 수가 Target보다 작다면 row하나 증가, 크다면 col하나 감소시켜서 값을 찾아갈 수 있다. 

 

예를 들어 아래 Matrix에서 target이 9라면, 15를 기준으로 다음과 같이 진행된다.

15 -(col감소)-> 11 -(col감소)-> 7 -(row증가)-> 8 -(row증가)-> 9

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

• Time complexity : O(m + n)
• Space Complexity : O(1)

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/806/

Explore - LeetCode