greentea31's Note

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

풀이 과정

행, 열 단위로 정렬되어 있는 2차원 배열에서 target 값이 존재하는지 여부를 판단하는 문제이다.

2차원 배열의 값들과 target의 값을 일일이 비교해보는 방법으로도 찾을수 있지만, 행 열 단위로 정렬되어 있다는 조건이 주어졌으므로 더 빠르게 문제를 해결할 수 있다.

시작 위치를 2차원 배열의 오른쪽 위 끝 혹은 왼쪽 아래 끝으로 잡은 뒤 배열 요소의 값과 target 값과의 대소 비교후 index를 바꾸면서 찾아가는 것이다. 이러면 모든 배열의 요소를 점검 할 필요가 없다.

소스 코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        
        m = len(matrix)
        n = len(matrix[0])
        
        a = 0
        b = n - 1
        
        while 0 <= a < m and 0 <= b < n:
            if matrix[a][b] == target:
                return True
            elif matrix[a][b] < target:
                a += 1
            else:
                b -= 1
        
        return False