[리트코드(LeetCode)] 240번 Search a 2D Matrix - 파이썬/python

문제

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

LeetCode - The World's Leading Online Programming Learning Platform

m x n 행렬에서 값을 찾아내는 효율적인 알고리즘을 구현하는 문제다. 행렬은 왼쪽에서 오른쪽, 위쪽에서 아래 오름차순으로 정렬되어 있다. 

예시

Example 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
Output: true

출처 : 리트코드 240번 문제

 

Example 2:

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
Output: false

풀이

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
            # 타겟이 크면 아래로 이동
            else:
                row += 1
                
        return False

 

- 행렬은 왼쪽에서 오른쪽, 위쪽에서 아래로 오름차순으로 정렬되어 있기 때문에 시작 위치는 행은 0으로, 열은 가장 오른쪽 끝으로 초기화한다.

- 타겟이 현재 위치 값보다 작으면 왼쪽, 크면 아래쪽으로 이동하면서 찾아간다.

- 타겟이 행렬에 있으면 True, 반복이 끝날 때까지 타겟이 행렬에 없으면 False를 반환한다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview