[LeetCode]Search a 2D Matrix

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

Search a 2D Matrix - LeetCode

 

문제 분석

주어진 2D Matrix에 target 값이 존재하는지를 찾는 문제입니다.

 

처음 시도한 답안

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

        while left <= right:
            mid = (left+right) // 2

            if matrix[mid][0] <= target <= matrix[mid][-1]:
                break

            if matrix[mid][0] < target:
                left = mid + 1
            else:
                right = mid -1
        
        for num in matrix[mid]:
            if num == target:
                return True
        
        return False

 

접근 방법

1. 이분 탐색을 진행하면서 target이 속한 row index를 구합니다.
2. 해당 row를 순회하면서 target을 찾는다면 True 못찾는다면 False를 return 합니다.

문제의 제약조건으로 O(log(m*n)) 의 시간복잡도가 있었기에 이분 탐색을 활용 했습니다. 먼저 target의 위치할 수 있는 범위의 row index 값을 구했습니다. 그 뒤에 row를 순회하면서 정답을 구했습니다.

 

두번째로 시도한 답안

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

        left = 0
        right = (row*col)-1
        
        while left <= right:
            mid = (left+right) // 2
            num = matrix[mid//col][mid%col]

            if num == target:
                return True

            if num > target:
                right = mid-1
            else:
                left = mid+1

        return False

접근 방법

1. 이분 탐색을 사용하는 것은 동일합니다.
2. 숫자를 탐색할 때 이차원 grid를 1차원인 것처럼 생각합니다.
3. num이 위치한 곳을 구하기 위해서 matrix[mid // col][mid % col]의 연산을 활용합니다.
   mid 값을 col의 갯수로 몫을 구하는 연산을 한다면 어느 row에 위치한지 알 수 있습니다.
   mid 값을 col의 갯수로 나머지를 구하는 연산을 한다면 어느 col에 위치한지 알 수 있습니다.
4. 나머지는 이분탐색과 모두 동일합니다.

첫번째의 방법에 비해서 한번의 loop로 최적화한 방법입니다. 이차원의 요소들을 마치 1차원인 것처럼 생각하는 것이 최적화 포인트입니다. 

row는 몫을 구하는 연산, col은 나머지 연산으로 그 위치를 구할 수 있습니다. 굉장히 좋은 방법이라고 생각됩니다.