LeetCode 240. Search a 2D Matrix II

파이썬 알고리즘 인터뷰 69번(리트코드 240번) Search a 2D Matrix II
https://leetcode.com/problems/search-a-2d-matrix-ii/

나의 풀이

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in range(len(matrix)):
            if not matrix[row][0] <= target <= matrix[row][-1]:
                continue
            else:
                left, right = 0, len(matrix[row]) - 1
                while left <= right:
                    mid = left + (right - left) // 2
                    if matrix[row][mid] > target:
                        right = mid - 1
                    elif matrix[row][mid] < target:
                        left = mid + 1
                    else:
                        return True
        return False

다른 풀이

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False

        row, col = 0, len(matrix[0]) - 1

        while row < len(matrix) and 0 <= col:
            val = matrix[row][col]
            if val == target:
                return True
            elif val > target:
                col -= 1
            else:
                row += 1
        
        return False

• 오른쪽 위 또는 왼쪽 아래 구석에서 시작해서 target 과 대소비교하며 지그재그로 찾아간다. 알고나면 오히려 자연스러운 풀인데 이런 풀이를 떠올리지 못하고 그저 이진 탐색을 이용할 생각만 했다. 그런데 그림을 보면 오히려 이 풀이가 자연스럽다.