[LeetCode | Python] 240. Search a 2D Matrix II

느낀점

바이너리 서치 문제는 이미 익숙하니 이를 조금 더 응용할 수 있는 문제를 찾다가 아래 문제를 찾았고, 예상했던 것보다는 더 오래 생각에 잠겨야 했던 문제 입니다. 2차원 배열이라 바이너리 서치 두 번으로 풀 수 있을 것이라고 생각했는데, 그렇게 풀지는 못했습니다. 본질적인 문제를 고민하였다면 조금 더 쉽게 접근할 수 있었을 것이라는 생각이드는 문제였습니다.

문제

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

 

다음과 같은 특징을 가진 m x n 크기의 정수 행렬(matrix)에서 특정 값(target)을 효율적으로 찾는 알고리즘을 작성하세요.

• 각 행의 정수는 왼쪽에서 오른쪽으로 오름차순으로 정렬되어 있습니다.
• 각 열의 정수는 위에서 아래로 오름차순으로 정렬되어 있습니다.

풀이

리트코드 문제 예시

 

바이너리 서치를 두번 적용한다고 했을 때, 이 배열의 중심인 9에 집중해야 하는데, 몇가지 케이스를 생각했다면 쉽게 풀 수 있는 문제였다.

9를 중심으로 다음의 케이스를 생각해보자.

• 9에서 포인터가 출발한다고 할 때, 9보다 큰 10이 어디에 존재할 수 있는가
• 9에서 포인터가 출발한다고 할 때, 9보다 작은 5는 어디에 존재할 수 있는가

처음에는 9를 중심으로 4가지면이 있고 한면만 탐색하면 상당히 효율적으로 탐색할 수 있을 것 같았는데, 그건 착각이었다. 위의 케이스들을 고려해본다면 다음의 영역은 탐색을 해야만 한다.

• 9가 중앙에 있을 때, 10이 존재할 수 있는 위치는 일단은 9 아래줄에 올 수 있고, 그 이후 왼쪽면과 오른쪽 면 둘다 올 수 있다(3, 4 사분면). 또한, 9 위로는 9보다 작은 수들이기 때문에 오른쪽면에 올 수 있다 (2 사분면).
• 9가 중앙에 있을 때, 5가 존재할 수 있는 위치는 일단은 9 윗줄에 올 수 있고, 그 이후 왼쪽면과 오른쪽 면 둘다 올 수 있다(1, 2 사분면). 또한, 9 아랫줄로는 9보다 큰 수들이기 때문에 왼쪽면에만 올 수 있다 (1 사분면).

즉 처음에 생각했을 때는 네 영역에서 한 영역만 탐색할 수 있을 줄 알았는데, 반대로 한 영역만 제외하고 다 탐색해야만 한다. 그래서 코드를 다음과 같이 바꾸게 됬다. 세로줄은 반복문으로 다 돌게 하고 가로줄은 바이너리 서치를 하되, 약간의 속도의 이점을 얻기 위해 스코프를 좀 조정하는 방식으로 코드를 작성했다.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        sn, ln = 0, len(matrix[0])-1
        cm = (sn+ln) // 2

        def bs(lst, sn, ln):
            while sn <= ln:
                mn = (sn+ln) // 2
                if lst[mn] == target:
                    return True
                elif lst[mn] > target:
                    ln = mn-1
                elif lst[mn] < target:
                    sn = mn+1
            return False

        for rlst in matrix:
            if rlst[cm] < target:
                if bs(rlst, cm, ln):
                    return True
            elif rlst[cm] > target:
                if bs(rlst, sn, cm):
                    return True
            elif rlst[cm] == target:
                return True

        return False

 

결과

• 시간복잡도: $ O(M * Log(N)) $
• 공간복잡도:  $ O(1) $