[리트코드] Search a 2D Matrix 2(python)

리트코드, Search a 2D Matrix 2_이차원 리스트 탐색하기 2

Search a 2D Matrix II - LeetCode

TL;DR

• 이진 탐색(Binary search)

문제 요약

1. m * n 크기의 2차원 정수 리트스 matrix에서 target을 찾는 효율적인 알고리즘을 작성하라.
2. 각 행(row)에서 숫자는 좌에서 우로 오름차순 정렬되어 있다.
3. 각 열(column)에서 숫자는 위에서 아래로 오름차순 정렬되어 있다.

 

- 좌에서 우로, 위에서 아래로 정렬된 2차원 리스트에서 target을 찾는 문제이다.

- 정렬된 리스트에서 원하는 값을 찾는 문제는 Binary search를 통해 문제를 해결할 수 있다.

입출력 형태

입출력 예시

풀이

내가 푼 방법은 각 행(row)에서 target을 찾고 행에서 존재하지 않으면 다음 행으로 넘어가는 방법이다. 이 방법의 시간 복잡도를 계산하자면 O(mlogn)으로 O(m * n)에 비해서 좋다고 생각한다.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        import bisect
        # row에서 못찾으면 다음 row로 넘어가는 방법
        for i in range(len(matrix)):
            index = bisect.bisect_left(matrix[i], target)
            
            if index < len(matrix[i]) and matrix[i][index] == target:
                return True
        
        return False

 

각 행에 target이 있는 index가 존재하는지 찾는다. 만약 존재한다면 True를 반환하고 그렇지 않으면 False를 반환한다.

 

다른 풀이로는 같이 스터디를 진행하는 분께서 제안해준 풀이이다. 2차원 리스트를 1차원 리스트로 변환하여 1차원 리스트에서 binary search를 통해 원하는 값을 찾는 방법이다.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        nums = []
        for item in list(zip(*matrix)):
            nums += item
        nums.sort()
        
        import bisect
        index = bisect.bisect_left(nums, target)
        if index < len(nums) and nums[index] == target:
            return True
        return False

 

2차원 배열을 1차원으로 변환해준다. 이 때, zip과 *를 써서 각 행을 item에 담아 nums에 추가해준다. Binary search를 수행하기 위해서는 정렬이 전제 조건으로 필요하기 때문에 정렬을 수행해준다. 이후 만든 1차원 리스트에 대해 binary search를 통해 원하는 값을 찾고, 있으면 True를 없으면 False를 반환하면 된다.

굳이 시간 복잡도를 계산하자면 O(mnlog(mn))라고 볼 수 있겠다. m과 n의 값 자체가 1 ~ 300으로 크지 않기 때문에 앞서 푼 방법과 시간 상의 큰 차이는 나지 않는다.