LC 74. Search a 2D Matrix

2차원 Matrix에서 이진탐색하는 문제

• 문제 보고 matrix를 반복문 돌려서 row 배열 하나씩 target 값을 찾는 이진탐색을 진행하자고 생각했다.

• 그렇게 풀어봤는데 문제없이 답이 나오긴 했다.

• 근데 다른 풀이 방법을 보니 이진탐색을 두 번 적용하는 경우가 대부분이었다.

  • target 값의 따라 어떤 row를 탐색할지 찾고

  • 찾은 row에서 다시 이진탐색으로 target 값이 있는지 찾더라.

• 내 풀이는 운이 좋아서 풀린 것 같고, target이 범위에 포함되는 row를 찾고 그 다음에 target을 찾는게 이 문제 풀이 정석이라고 생각된다.

내 풀이:

• 반복문으로 2차원의 row를 하나씩 꺼낸다.
• 각 row 마다 이진탐색을 적용해 target 값을 찾아낸다.

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

시간복잡도는 각 행마다 모두 이진탐색을 적용하기 때문에 O(NlogM)이다.

• matrix 반복문: N,
• 이진탐색: logM
  

정석 풀이:

• 각 행이 오름차순으로 정렬되어 있기 때문에, target을 포함하고 있는 범위의 행을 찾는다.
• 찾은 행에서 이진탐색으로 target 값을 찾는다.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 2차원 배열의 행과 열 개수
        ROWS, COLS = len(matrix), len(matrix[0])

        # target이 포함되는 범위를 갖는 행 찾기
        top, bottom = 0, ROWS - 1
        while top <= bottom:
            row = (top + bottom) // 2
            if target > matrix[row][-1]:
                top = row + 1
            elif target < matrix[row][0]:
                bottom = row - 1
            else:
                break
        
        # while 문을 정상적으로 다 돌았지만 target이 포함되는 row가 없다면 return false
        if not (top <= bottom):
            return False
        
        # target을 포함하는 row
        row = (top + bottom) // 2

        # row에서 target을 찾는 이진탐색
        start, end = 0, COLS - 1
        
        while start <= end:
            mid = (start + end) // 2
            if matrix[row][mid] < target:
                start = mid + 1
            elif matrix[row][mid] > target:
                end = mid - 1
            else:
                return True
        return False

시간복잡도는 이진탐색을 두 번 적용하므로
O(logM + logN)