240. Search a 2D Matrix II

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The 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.

My Answer 1: Accepted (Runtime: 168 ms - 34.74% / Memory Usage: 20.5 MB - 68.94%)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for i in matrix:
            if target in i:
                return True
        return False

if target in i: in 이 이중 for 문까지 가는 길을 막아줬다.

근데 당연히 이걸 답으로 원하진 않을듯

Greedy

Solution 1: Runtime: 172 ms - 21.47% / Memory Usage: 20.5 MB - 51.74%

class Solution:
    def searchMatrix(self, matrix, target):
        ## RC ##
        ## APPROACH : GREEDY ##
        ## Similar to Leetcode: 74. Search A 2D Matrix ##
        
        # 1. First, we initialize a (row, col) pointer to the bottom-left of the matrix.
        # 2. If the currently-pointed-to value is larger than target we can move one row "up". 
        # 3. Otherwise, if the currently-pointed-to value is smaller than target, we can move one column "right".
        
		## TIME COMPLEXITY : O(N + M) ##
		## SPACE COMPLEXITY : O(1) ##
                
        i, j = len(matrix) - 1, 0
        while(i >= 0 and i < len(matrix) and j >=0 and j < len(matrix[0])):
            if(matrix[i][j] == target): return True
            if(matrix[i][j] > target):  i -= 1
            if(matrix[i][j] < target):  j += 1              
        return False

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란
"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"
라는 모토를 가지는 알고리즘 설계 기법이다.(https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

target 값보다 크면 row up, 작으면 column right

외우자!!!