[Python][LeetCode] Search a 2D Matrix II(2D 매트릭스 검색)

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

Search a 2D Matrix II - LeetCode

문제 설명:

행렬이 주어졌을때 target의 값을 구하는 문제이다.

 

 

방법1

• 플래그를 설정해준다. 만약 target을 찾으면 true값을 반환하도록 한다.
• 행렬에서 한 행씩 가져오도록 한다.
• 한행에서 이진탐색을 해 찾은 인덱스를 반환받도록 한다.
• 실제 행렬에 있는 값과 타겟이 같은 값인지 확인하고 맞으면 플래그를 전달한다.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        flag = False
        for idx,col in enumerate(matrix):
            num_idx = bisect.bisect_left(col, target)
            if num_idx < len(matrix[0]) and matrix[idx][num_idx] == target:
                flag = True

        return flag

 

방법2

• row = 0, col = 행렬의 가장 마지막 행
• 만약 target 이 행렬[row][col]의 값과 같으면 true 반환한다.
• target이 행렬[row][col]의 값보다 작으면 col의 위치를 위로 올려준다.
• target이 행렬[row][col]의 값보다 크다면 row의 위치를 오른쪽으로 올려준다.

        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