[Leet Code 내 맘대로 풀이] 74. Search a 2D Matrix

문제 설명

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

자세한 문제는 위 링크 참고. 정렬된 매트릭스가 주어졌을때, target 값이 주어지면 해당 값이 있으면 True를 출력하고 없으면 False를 출력하는 문제다.

첫번째 풀이

그저 매트릭스에 있는 row별로 target값이 있는지 체크한다. 참고로 python의 in 연산자는 내부적으로 선형 탐색을 하므로 O(n)의 시간 복잡도가 소모된다고 한다. 즉 row의 length 길면 시간이 길어진다.

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

두번째 풀이

바이너리 서치로도 풀 수 있는데, 이는 위에서 말한 in 연산으로 target 값을 찾을때 O(n)이 소요되므로 조금 더 시간을 단축해보기 위함이다. 먼저 매트릭스 자체가 정렬된 상태니깐, target 값이 range에 있는 row들만 대상으로 binary search를 해봤다.

def bin_search(row: List[int], target):
    left = 0
    right = len(row) - 1

    while left <= right:
        mid = int((left + right)/ 2)

        if row[mid] == target:
            return True

        if row[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return False
    
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            if row[0] == target or row[-1] == target:
                return True
            elif row[0] < target < row[-1]:
                return bin_search(row,target)
            else:
                continue