[LeetCode 풀이/python] 74. Search a 2D Matrix (medium)

문제 설명: m x n 행렬에서 하나의 값 value 을 찾는 효율적인 알고리즘을 작성하시오. 해당 행렬은 다음과 같은 특성을 지니고 있다:

• 각 행의 정수들은 왼쪽에서 오른쪽으로 (오름차순) 정렬되어 있다
• 각 행의 첫번째 정수는 이전 행의 마지막 정수보다 크다

(Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.)

 

예시 1)

입력: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3  -->  출력: true

 

예시 2)

입력: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13  -->  출력: false

 

제한 조건:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 이진 탐색(binary search) 를 두 번 이용!
  • 우선 첫번째 이진 탐색을 통해 타겟 요소가 존재할 수 있는 범위에 해당하는 행(row) 을 구함
    • 일반적인 이진 탐색과 달리 mid idx 에 해당하는 값이 타겟 요소와 완전히 일치하지 않을 가능성이 높고 존재할 법한 범위를 구하기 위함이므로 if 문 조건 설정이 다소 까다롭...!  --  별도 함수 find_row 로 구현
  • 첫번째 이진 탐색 결과 타겟 요소가 존재할 수 있는 행을 구하면, 각 행은 이미 정렬되어 있으므로 두번째 이진 탐색을 통해 해당 요소의 존재 여부를 확인

 

• 코드 구현

def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
    l, r = 0, m-1
        
    row = find_row(matrix, l, r, target)
    l, r = 0, n-1
    while l <= r:
        mid = (l+r)//2
        if target < matrix[row][mid]: r = mid-1
        elif target > matrix[row][mid]: l = mid+1
        else: return True
    return False      
    
    
def find_row(matrix, l, r, target):
    while l < r:
        mid = (l+r)//2
        if target < matrix[mid][0]:
            r = mid-1
        elif target > matrix[mid][-1]: 
            l = mid+1
        else: return mid
            
    mid = (l+r)//2
    return mid

 

• 결과
  • 각 이진 탐색이 O(n log n) 의 시간 복잡도를 요구하므로 총 O(m log m) + O(n log n) = O(m log m + n log n)
  • 무난하게 통과 ~_~