[1스4코2파] # 189. LeetCode 74. Search a 2D Matrix

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (189차)
[4코1파] 2023.01.13~ (181일차)
[1스4코1파] 2023.04.12~ (92일차)
[1스4코2파] 2023.05.03 ~ (70일차)

Today :

2023.07.11 [189일차]
binary_search
Leetcode 74 Search a 2D Matrix

74. Search a 2D Matrix

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

문제 설명

M x N matrix가 주어질 때, 해당 matrix는
(1) row 기준 오름차순이고
(2) 각 row의 첫 번째 원소는 이전 row의 원소보다 큼

target이 주어졌을 대, 해당 matrix안에 target 원소가 있으면 True, 아니면 False를 return 함
O(log(M*N))의 시간복잡도로 풀어야함

문제 풀이 방법

시간복잡도 O(log(M*N)) 으로 주어졌으므로 binary_search로 풀기

내 코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])

        top, bottom = 0, ROWS - 1
        while top <= bottom:
            row = (top + bottom) // 2
            if target > matrix[row][-1]:
                top = row + 1
            elif target < matrix[row][0]:
                bottom = row - 1
            else:
                break

        if not (top <=bottom):
            return False
        row = (top + bottom) // 2
        left, right = 0, COLS - 1
        while left <= right:
            mid = (left + right) // 2
            if target > matrix[row][mid]:
                left = mid + 1
            elif target < matrix[row][mid]:
                right = mid - 1
            else:
                return True
        return False

증빙

여담

ㅗ