[LeetCode 240] Search a 2D Matrix II

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

Search a 2D Matrix II - LeetCode

 

Think

정렬된 mXn행렬과 target값이 주어지고, 행렬에서 target값이 존재하는지 T/F를 구하는 문제

행렬은 왼->오, 위->아래 방향으로 오름차순 정렬되어있음

존재하면 true 리턴

 

이진 검색 문제처럼 보이지만 이진 검색 보다는 다른 탐색을 사용하여 풀이해야 함

1. 첫 행의 맨 마지막 수를 택하여 비교 후 target값보다 작으면 왼쪽으로, 크면 아래로 이동하며 찾음

2. 파이썬 다운 한줄 풀이

 

 

Solution

방법 1.

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        
        #예외
        if not matrix :
            return False
        
        #행과 열 인덱스 초기화 - 첫행, 마지막 열로 초기화함
        row = 0
        col = len(matrix[0]) - 1 #참고로 그냥 len(matrix)는 행 개수임
        
        while row <= len(matrix) - 1 and col >= 0 : #행과 열 각각이 반대쪽 끝에 도달할 때까지
            if matrix[row][col] == target :
                return True
            #target값보다 크면 왼쪽으로
            elif matrix[row][col] > target :
                col -= 1
            #target값보다 작으면 아래로
            elif matrix[row][col] < target :
                row += 1
        
        return False #못 찾으면

 

방법 2. 파이썬 답게

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        
        # 행렬의 행row를 한 줄씩 돌면서 해당 행에 target이 존재하는 지 확인함. 
        # any() 는 True/False로 이루어진 배열을 넣었을 때 True가 하나라도 있으면 True 반환
        return any(target in row for row in matrix)

 

Get