[leetcode] 74. Search a 2D Matrix (python)

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

난이도 : Medium

 

풀이1  --- Brute Force

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

이미 정렬이 되어있는 상태이기 때문에 각 행 마지막 열의 범위를 체크해서 그 안에 존재하면 true 반환한다.
너무나 직관적이고 단순한 방법이다.

 

풀이2  --- Binary Search Tree 

class Solution:
     def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        lo, hi = 0, len(matrix) - 1
        while lo <= hi:
            midRow = (lo + hi) // 2
            row = matrix[midRow]
            if target < row[0]: hi = midRow - 1
            elif target > row[-1]: lo = midRow + 1
            else:
                l, h = 0, len(row) - 1
                while l <= h:
                    mid = (l + h) // 2
                    if row[mid] == target: return True
                    elif target > row[mid]: l = mid + 1
                    else: h = mid - 1
                return False

'이미 정렬이 되어있는 배열에서 원소를 찾는다!'  -> 이진트리를 떠올리는 것은 어렵지 않을 것이다.
풀이1과 비교해보면 시간이 약 2배나 줄었다.

위에가 풀이2(binary search tree), 아래가 풀이1(Brute Force)

이 방법으로 풀라고 난이도가 medium인가

 

풀이3  --- Python any() 이용

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        return any(target in row for row in matrix)

파이썬 공부하면서 느끼는 거지만 허무할 정도로 진짜 별 함수가 다 있다.....

파이썬 내장함수 중에 any()와 all() 함수가 존재한다. 모두 argument로 iterable한 객체를 받으며 이 객체를 검사해 True/False를 반환한다.

• any() : 하나라도 True면 True
• all() : 모두 True를 만족해야 True 반환