[LeetCode] 1901. Find a Peak Element II

- Problem

1901. Find a Peak Element II

- 풀이 1 (brute-force)

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        def greater_cell(y, x):
            curr = matrix[y][x]
            if matrix[y-1][x] < curr and matrix[y+1][x] < curr and matrix[y][x-1] < curr and matrix[y][x+1] < curr:
                return True
            return False

        M, N = len(mat), len(mat[0])

        matrix = [[-1] * (N+2)]

        for i in range(M):
            matrix.append([-1] + mat[i] + [-1])

        matrix.append([-1] * (N+2))

        for i in range(1, M+1):
            for j in range(1, N+1):
                if greater_cell(i, j):
                    return [i-1, j-1]

- 결과

우선, 문제에서 제시한 시간 복잡도 O(NlogM)) or O(MlogN) 풀이 방법이 떠오르지 않아 완전 탐색으로 풀어봤다.

결과에서 보다시피, 굉장히 느린 시간 복잡도와 비효율적인 공간 복잡도를 가진다.

- 풀이 2 (이분 탐색)

...언젠가 다시 풀어볼게요