1 분 소요

문제

Find a Peak Element II - LeetCode

접근 방법

  1. BruteForce
    • 모든 행, 열에 대해 좌,우,위,아래 값을 비교 → peak를 찾는다 : O(NM)
  2. 내 접근 방법
    • 각 행별로 binarySearch를 통해 peak 찾아서 해당 칸의 위, 아래 값과 비교 → 최종 peak 구한다.
    • 틀림 : 각 행별로 peak가 여러 개 있어도 한개만 탐색함 → 내가 찾은 peak의 위, 아래 값이 peak보다 클 경우, 다른 peak가 정답 → 다른 peak를 탐색해야하는데 binarySearch로는 어려움
  3. solution
    • 각 컬럼 별로 max 값을 갖는 row를 찾는다. 즉, mat[maxRow][col] 은 해당 col에서 최대 값을 갖는다.
    • mat[maxRow][col-1] < mat[maxRow][col] > mat[maxRow][col+1]을 만족할 경우 peak 탐색 성공
    • 즉, row에 대해서는 O(N)으로 완전탐색하되, col에 대해서는 이분탐색을 한다. → O(NlogM)
from typing import List
# 접근 방법 : 각 행별로 peak 찾아서 해당 칸의 위, 아래 값과 비교 -> 최종 peak 구한다.
# 틀림 -> 각 행별로 peak을 하나만 찾음 -> row에 peak가 여러 개이고, 내가 찾은 peak가 아니라 다른 peak가 정답일 경우, 구하지 못한다
# 그래서 각 row 별로 peak를 리스트로 찾으려 했으나 그렇게 하면 O(nlogm)시간 복잡도가 아님

# 정렬되지 않은 array에서 이진탐색으로 peak 찾기
# Time Complexity : M*log(N).
def findPeakGrid(mat: List[List[int]]) -> List[int]:
    startCol = 0
    endCol = len(mat[0])-1

    while startCol <= endCol:
        # Pick the middle column.
        midCol = (startCol+endCol)//2
        maxRow = 0

        # 해당 midCol에서 maxRow를 찾음  -> 해당 컬럼에서 가장 큰 값이라는 전제 : O(M)-> 좌우 컬럼에 대해서만 비교하면 됨
        for row in range(len(mat)):
            maxRow = row if (mat[row][midCol] >= mat[maxRow][midCol]) else maxRow

        # mat[maxRow][midCol] 값이 peak인지 판별
        leftIsBig = midCol-1 >= startCol and mat[maxRow][midCol-1] > mat[maxRow][midCol]
        rightIsBig = midCol+1 <= endCol and mat[maxRow][midCol+1] > mat[maxRow][midCol]

        # If the row-neighbours of this element are smaller, then we found a 2D peak.
        if (not leftIsBig) and (not rightIsBig): # we have found the peak element
            return [maxRow, midCol]
        elif rightIsBig:        # if rightIsBig, then there is an element in 'right' that is bigger than all the elements in the 'midCol'
            startCol = midCol+1     # so 'midCol' cannot have 'peakPlane'
        else:
            endCol = midCol-1

    return []

mat = [[7,2,3,1,2],[6,5,4,2,1]]
print(findPeakGrid(mat))

참고