LeetCode Top Interview 150) Search a 2D Matrix

Question

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

---

---

정렬된 2차원 정수 리스트 matrix가 있고 주어진 target 변수가 해당 matrix내에 존재하는지 bool값으로 반환하는 문제입니다. 로그 시간복잡도를 신경써야합니다.

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = self.search([matrix[i][0] for i in range(len(matrix))],target,is_insert=True)
        return self.search(matrix[row], target, is_insert=False)

    def search(self, nums: List[int], target: int, is_insert: bool) -> int:
        if nums[-1] < target and is_insert:
            return len(nums)-1

        l,r = 0,len(nums)-1

        while l+1 < r:
            m = (l+r)//2
            if nums[m] < target:
                l = m
            elif nums[m] > target:
                r = m
            else:
                return m
        if is_insert:
            return l if nums[r] != target else r
        else:
            return True if nums[l] == target or nums[r]==target else False

• search() 함수 : 이분 탐색으로 target을 탐색합니다. 인자는 다음과 같습니다.
  • nums : 1차원 정수 리스트입니다.
  • target : 목표로하는 정수값입니다.
  • is_insert : target을 삽입하는지, 찾는지 결정합니다. 마지막 반환값을 제외하고는 존재여부와 인덱스 탐색 알고리즘이 거의 비슷합니다. 그래서 인자에 따라 결과를 도출하는 방식을 바꾸는 방법을 선택했습니다.
• 첫번째 열을 search()의 nums인자로 넣어서 찾고자 하는 target이 어느 행에 있는지 row값을 찾습니다.
• search() 함수의 is_insert=False를 통해 문자열 내에 target이 존재하는지 반환하도록 합니다.

---

이분탐색함수를 이전에 구현해본 것을 가져와서 문제 조건에 맞게 약간의 수정을 했습니다.

알고리즘이 어렵운 문제는 아니였습니다. 이분탐색 함수를 이용해 행, 열 한 번 씩 탐색하는 문제였습니다.