LeetCode 74(Search a 2D Matrix, Python)

1. 문제 링크

• Search a 2D Matrix - LeetCode

Search a 2D Matrix - LeetCode

2. 문제 설명

• 주어진 m x n 행렬(matrix)에 대해 target이 행렬 내에 존재하는지 여부를 판단하는 문제
• 행렬은 각 행이 오름차순으로 정렬되어 있고,
• 각 행의 첫 번째 요소는 그 행의 마지막 요소보다 항상 작음
• 또한, 각 행의 첫 번째 요소는 그 위 행의 마지막 요소보다 항상 큼
• 예시) matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3이면 3이 있으므로 True

3. 처음 풀이

• 어렵지 않다. 이진 검색을 하면 된다. 우선 목표 값이 존재한다면 어느 행에 있는 지를 조사한다. 이때는 각 행의 첫번 째 요소만 보면 되기 때문에 이진 검색을 하면 시간 복잡도 O(logm)이 걸린다.
• 다음으로 그 행에 목표 값이 존재하는 지 이진 검색하면 시간 복잡도 O(logn)이 걸린다.
• 따라서 최종 시간복잡도는 O(logmn)이다.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    	# 행렬의 첫 번째 값이 목표보다 큰 경우나 마지막 값이 목표보다 작은 경우 False 반환
        if matrix[0][0] > target:
            return False
        if matrix[-1][-1] < target:
            return False
            
        # 이진 탐색을 위한 초기 변수 설정
        up, down = 0, len(matrix) - 1
        mid = (up + down)//2
        
        # 행에 대한 이진 탐색
        while up < down:
            if matrix[mid][0] == target or matrix[mid][-1] == target:
                return True
            elif matrix[mid][0] > target:
                down = mid - 1
            elif matrix[mid][-1] < target:
                up = mid + 1
            else:
                up = mid
                down = mid
            mid = (up + down)//2
        
        # 찾아낸 행에서 열에 대한 이진 탐색
        left, right = 0, len(matrix[0]) -1
        center = (left + right)//2
        while left <= right:
            if matrix[mid][center] == target:
                return True
            elif matrix[mid][center] > target:
                right = center - 1
            else:
                left = center + 1
            center = (left + right)//2
        
        # 목표가 없는 경우 False 반환
        return False

4. 다른 풀이

• 행렬을 하나의 오름차순 리스트로 보고 이진 검색을 한 번만 할 수도 있다.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1

        while left <= right:
            mid = (left + right) // 2
            mid_row, mid_col = divmod(mid, n)

            if matrix[mid_row][mid_col] == target:
                return True
            elif matrix[mid_row][mid_col] < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

5. 배운 점

• 이번 문제는 많이 풀어본 이진 검색이라 새로운 점은 없다. 행과 열을 따로 보지 않고 한 번에 처리한 것도 특별히 tricky하진 않다.