[리트코드] 240. 2D 행렬 검색 2 (Python)

LeetCode - The World's Leading Online Programming Learning Platform

문제

m x n 그래프에서 target 값이 있다면 Treu 없다면 False를 출력해라

과정

• 이진탐색을 이용하여 풀어준다.

 

입력

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

출력

True

 

풀이

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        start, end = 0, len(matrix[0])-1
        while start < len(matrix) and end >= 0:
            if matrix[start][end] < target:
                start += 1
            elif matrix[start][end] > target:
                end -= 1
            else:
                return True
        return False

 

한 줄 씩 해석해보기

start, end = 0, len(matrix[0])-1

• 0과 마지막 첫번째 행의 마지막 인덱스 까지 투포인터 생성
• 한 행씩 탐색한다.

while start < len(matrix) and end >= 0:
    if matrix[start][end] < target:
        start += 1
    elif matrix[start][end] > target:
        end -= 1
    else:
        return True
return False

• start가 matrix 길이보다 커지거나 0이하가 되기 전까지 탐색한다.
• 만약 해당 좌표의 값이 target보다 작다면 start+=1
• target보다 크다면 end-=1
• 그게 아니라면 target과 값이 같은것이므로 True를 return한다.
• while문을 다 돌았다면 False를 return한다.