[leetcode 2024/02/24] 240. Search a 2D Matrix 2

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

Search a 2D Matrix II - LeetCode

 

1. 접근 방법

matrix에 대해서, 가로-세로로 구하고자 하는 수보다 작은 범위를 구해주었다.

 

이후, 좁혀진 범위에 대해서 다시 재귀적으로 가로-세로로 구하고자 하는 수보다 작은 범위를 구해주었다.

( repeat이라는 변수에 대해서도 + 1을 해주었다. )

그 과정 속에서 원하는 값을 찾으면 True를 반환해주었으며, repeat - row > 0 or repeat - column > 0 일 경우, 해당 값이 없다고 판단 False를 반환해 주었다.

 

그림으로 더 알아보자. 만약 14를 구한다고 가정해 볼 것이다.

이런식으로 가로, 세로 범위를 구하게 된다.

 

이후, 새로움 범위에 대해서 다시 search를 진행하게 된다.

 

새로운 범위에 대해서 또 search를 진행, 해당 단계에서는 14를 읽게 되므로 14를 찾았기에 True를 반환해 주었다.

 

만약 이 단계에서 14를 찾지 못하고 더 진행 했다면,  repeat - row > 0 or repeat - column > 0 이 조건에 걸리게 되어, False가 반환되었을 것이다.

 

2. 코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

        def find_value(target, repeat, row, column):
            if repeat - row > 0 or repeat - column > 0:
                return False

            for i in range(repeat, row + 1, 1):
                if matrix[repeat][i] >= target:
                    if matrix[repeat][i] == target:
                        return True
                    else:
                        row = i
                        break

            for i in range(repeat, column + 1, 1):
                if matrix[i][repeat] >= target:
                    if matrix[i][repeat] == target:
                        return True
                    else:
                        column = i
                        break

            return find_value(target, repeat + 1, row, column)

        row_o = len(matrix[0])
        column_o = len(matrix)
        return find_value(target, 0, row_o - 1, column_o - 1)