[리트코드] Search a 2D Matrix II

legowww·2021년 12월 22일
0

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


1. 전체 코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        k = []
        for i in range(len(matrix)):
            k.append(matrix[i][0])
        col = bisect_right(matrix[0], target)
        row = bisect_right(k, target)
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == target:
                    return True
        return False

처음 제출한 풀이이다. target보다 큰 row와 col은 제외하고 탐색한다. 하지만 row나 col이 matrix 행열의 길이와 같다면 완전탐색과 다름없다.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # return any(target in row for row in matrix)
        if not matrix:
            return False
        # 0행 마지막 열에서 시작
        row = 0
        col = len(matrix[0]) - 1
        while row <= len(matrix) - 1 and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1
            elif matrix[row][col] < target:
                row += 1
        return False

첫 행의 마지막 원소를 시작으로 값을 줄여나가는 풀이이다. 전체적인 코드의 형태가 투 포인터를 사용하는 코드와 비슷하다.


any를 효율적으로 사용하는 예시

# 1차원 배열에서 any
arr = [1, 3, 5, 7, 9]
result = [num > 10 for num in arr]
print(result)  # [False, False, False, False, False]
print(any(num > 10 for num in arr))  # False 아래와 동일한 결과
print(any(result))  # False


# 2차원 배열에서 any
arr = [[1, 3, 5, 7, 9], [2, 4, 6, 8, 10]]
ans = [5 in row for row in arr]
print(ans)  # [True, False]
print(any(row[0] > 5 for row in arr))  # False
print(any(5 in row for row in arr))  # True

any의 매개변수로 리스트 컴프리헨션을 통해 만들어진 True 또는 False로 구성된 리스트를 사용했다.

profile
티스토리 https://02082306.tistory.com/

0개의 댓글