240. Search a 2D Matrix II

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

Search a 2D Matrix II - LeetCode

Solution

class Solution:
    def searchMatrix(self, matrix, target):
        row, col = 0, len(matrix[0])-1
        while row < len(matrix) and col >= 0:
            if matrix[row][col] < target:
                row += 1
            elif matrix[row][col] > target:
                col -= 1
            else:
                return True
        return False

• 우측 위부터 시작한다.
• 타겟보다 작으면 row를 증가시키고 타겟보다 크면 col을 감소시킨다.
• 타겟을 만나면 True를 반환하고 못만나면 False를 반환한다.

 

• 원래 풀고 싶은 방법
  • 대각선을 살피면서 타겟보다 커지는 지점을 찾는다.
  • 행렬을 쪼개서 타겟이 있을 만한 곳을 같은 방법(재귀)으로 찾는다.
  • 재귀가 너무 깊어서 에러가 발생한다.