리트 코드 - 2D 행렬 검색 II 240번

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

Search a 2D Matrix II - LeetCode

 

** 내 풀이

import bisect
from typing import List


class Solution:
    #1 180ms, 20.5MB
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for i in range(len(matrix)):
            if matrix[i][0] <= target:
                if target in matrix[i]:
                    return True
        return False

 

먼저 행을 살핀다.

행과 열이 모두 정렬되어있다는 점을 활용한 것인데,

행의 맨 앞이 우선은 타겟보다 작아야, 탐색이 가능하다.

따라서 이를 걸러내주고,

그 걸러내진 행들의 열을 탐색해가며 값이 있는지 체크하는 식이다.

 

** 결론

이진 탐색은 투포인터나, 파이썬다운 방식, 내장 함수 활용 등이 효율적이고, 성능도 좋다.