240. Search a 2D Matrix II

Search a 2D Matrix II - LeetCode

1. Brute Force

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        temp = []
        for item in matrix:
            temp += item
        if target in temp:
            return True
        return False

그냥 이렇게 배열을 정말 탐색해도 통과는 된다.

2. 이진 탐색

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

정렬이 되어있는데 탐색을 해야 한다면 이진 탐색을 한번 생각해보면 좋다.

행, 열 모두 오름차순으로 정렬되어있기 때문에 위 풀이가 가능하다.

 

이진 탐색은 생각했지만 예쁘게 푸는 법을 스스로 찾진 못했다.