[LeetCode] 74. Search a 2D Matrix (Python)

https://leetcode.com/

1. 문제

https://leetcode.com/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-interview-150

LeetCode - The World's Leading Online Programming Learning Platform

 

---

2. 문제 설명

Each row is sorted in non-decreasing order.

→ 각 행은 오름차순으로 정렬되어 있다.

 

The first integer of each row is greater than the last integer of the previous row.

→ 각 행의 첫번째 정수는 앞선 행의 마지막 정수보다 크다.

 

위의 규칙으로 저장된 2차원 배열에서 target 값이 있는지 찾아야 한다.

단, O(log(m * n))의 시간복잡도로  풀 수 있도록 해야한다.

 

정수 값 저장 방식

---

3. 문제 풀이

위의 설명과 같이 matrix는 2차원 배열이고 정렬되어 있는 상태이다.

이 문제는 target 값이 matrix에 존재하는지 판별해야 하는데 O(log(m * n))의 시간복잡도로 제한되어 있다.

모든 값과 비교해가면서 찾는 방법은 배열이 길어질수록 시간이 오래걸린다.

그러므로 정렬되어 있는 상태를 이용하며 찾는 범위를 줄여가는 이분탐색을 사용했다.

• 행을 이분탐색한다.
  • 현재 행의 가장 작은 값과 가장 큰 값 사이에 target이 존재하면 break
  • 존재하지 않으면 return False
• 열을 이분탐색한다.
  • target 값이 존재하면 return True
  • 존재하지 않으면 return False

즉, 나는 행과 열을 따로 이분 탐색하며 값의 존재 여부를 판별했다.

---

4. 코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = len(matrix) #행
        col = len(matrix[0]) #열

        # 행 탐색
        start = 0
        end = row-1
        flag = False
        while start <= end :
            mid = (start + end) // 2
            if matrix[mid][0] <= target and matrix[mid][col-1] >= target :
                row = mid
                flag = True
                break
            
            if matrix[mid][0] >= target :
                end = mid - 1
            else :
                start = mid + 1
        
        if not flag : #행의 범위에 포함되어 있지 않을 경우
            return False
        
        # 열 탐색
        start = 0
        end = col-1
        while start <= end :
            mid = (start + end) // 2
            if matrix[row][mid] == target :
                return True
            if matrix[row][mid] > target :
                end = mid - 1
            else :
                start = mid + 1
        
        return False