Leetcode Python - 74. Search a 2D Matrix

Leetcode #74 - Search a 2D Matrix

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. matrix을 집중적으로 풀어보겠습니다.

리트코드의 문제 74 ‘Search a 2D Matrix’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 이진탐색을 두 번 써서 해당 값이 존재하는지 탐색하는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def searchMatrix(self, matrix, target):
        low = 0
        high = len(matrix)-1
        target_row = 0
        while low <= high:
            mid = (low+high)//2
            
            if target < matrix[mid][0]:
                high = mid-1
            elif matrix[mid][-1] < target:
                low = mid+1
            else:
                target_row = mid
                break
        
        low = 0
        high = len(matrix[0])-1
        target_col = 0
        while low <= high:
            mid = (low+high)//2
            
            if target < matrix[target_row][mid]:
                high = mid-1
            elif matrix[target_row][mid] < target:
                low = mid+1
            else:
                return True
        return False

시간복잡도는

• O(logn) : 이진탐색(logn)으로 row를 결정 + 이진탐색(logn)으로 column을 결정

공간복잡도는

• O(1) : on place