1 minute read

240. Search a 2D Matrix II

문제 링크

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

문제 설명

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

제한 사항

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • All the integers in each row are sorted in ascending order.
  • All the integers in each column are sorted in ascending order.
  • -10^9 <= target <= 10^9

입출력 예 #1

  1. Input : matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
  2. Output : true

입출력 예 #2

  1. Input : matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
  2. Output : false

문제 풀이

  1. 첫 행의 맨 뒤 항목과 target 값 비교하여 target값 보다 작으면 다음 행, target 보다 크면 열을 감소시키며 탐색
  2. 파이썬다운 풀이 방식
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 예외 처리
        if not matrix:
            return False
        
        # 첫 행의 맨뒤
        row = 0
        col = len(matrix[0]) - 1

        while row <= len(matrix) - 1 and col >= 0:
            if target == matrix[row][col]:
                return True
            # 타겟이 작으면 왼쪽으로 이동
            elif target < matrix[row][col] :
                col -= 1
            elif target > matrix[row][col] :
                row += 1
        return False

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

Comments

You May Also Enjoy