[LeetCode] 74 | Search a 2D Matrix | Python

---

문제 링크: https://leetcode.com/problems/search-a-2d-matrix/

---

문제

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 from left to right.
• The first integer of each row is greater than the last integer of the previous row.

---

조건

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• $-10^4$ <= matrix[i][j], target <= $10^4$

---

내 풀이

처음부터 끝까지 차례로 봐도 되지만, 이 문제의 조건과 다르게 m, n이 클 때를 대비해서 다음과 같이 짰다.

 

각 줄의 맨 처음 숫자(matrix[h][0])을 이용해 어느 줄에 target이 존재할 지 파악한다.

그 줄을 차례로 훑으며 target이 있으면 True를 리턴하고, target보다 숫자가 커지면 target이 존재하지 않는 것이기 때문에 False를 리턴한다.

---

코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        H, W = len(matrix), len(matrix[0])
        
        for h in range(H):
            if matrix[h][0] > target:
                h -= 1
                break
        
        for w in range(W):
            if matrix[h][w] == target:
                return True
            elif matrix[h][w] > target:
                return False