[Binary Search] LEETCODE.74. Search a 2D Matrix

문제풀이

이번 문제는 두번의 이진탐색으로 해결가능한 문제이다.
우선 첫번째 열 기준으로 이진탐색을 통해 어떤 행에 Target이 위치할지 판단하고 해당 행을 추출하여 한번더 이진탐색을 통해 Target 값이 있는지 확인한다.

코드

from bisect import bisect_left
from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n_col, n_row = len(matrix), len(matrix[0])

        # 최솟값, 최대값 기준에 존재할 수 없는 경우 정의
        if matrix[0][0] > target or matrix[n_col-1][n_row-1] < target:
            return False

        # 각 행의 첫 번째 요소를 가져와서 이진 탐색 대상으로 설정 (target이 몇 번째 행인지 확인)
        target_col = [row[0] for row in matrix]
        target_row = bisect_left(target_col, target)

        # 타겟이 첫 번째 열에 있으면 해당 행에서 바로 찾을 수 있으므로 로직 처리
        if target_row < len(target_col) and target_col[target_row] == target:
            return True

        # 이진 탐색으로 목표 값을 가진 행에서 열 인덱스를 찾음.
        target_list = matrix[target_row - 1]
        target_col_index = bisect_left(target_list, target)

        # 목표 값이 행 또는 열 범위를 벗어나면 False를 반환
        if target_col_index >= n_row or target_row > n_col:
            return False

        # 찾은 값을 확인하여 결과를 반환
        return matrix[target_row - 1][target_col_index] == target

Lookback

1. bisect 라이브러리를 통해 간단히 해결할 수 있어 기뻤다.
2. 아직 실력이 부족하지만 소스를 단순화하려고 노력을 인위적으로 많이 하고 있는데 이전에 연습했던 것들을 써먹을 수 있었던 좋은 기회(?)였다

• target_col = [row[0] for row in matrix]
• return matrix[target_row - 1][target_col_index] == target