문제 링크 : https://leetcode.com/problems/find-peak-element/
간단하게 설명하면 peak element의 인덱스를 반환하는 문제이다.
peak element란 :
Peak Element : 봉오리처럼 우뚝 솟아있는 요소
단순히 해당 배열(nums)에서 가장 큰 숫자를 반환하는게 아니라 양 옆과 비교했을 떄 두 숫자보다 커서 봉오리처럼 우뚝 솟아있는 지점을 의미한다(이것때문에 문제 풀고 이해하는데.. 몇 시간을.......)
따라서 오름차순으로 정렬이 되어있지 않아도 binary search를 이용하여 문제를 푸는 것이 가능하다.
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
l = 0
r =len(nums) -1
while l<r:
mid = (l+r) // 2
if nums[mid]<nums[mid+1]:
l = mid+1
else:
r = mid
return l
인덱스의 맨 앞과 맨 뒤를 각각 l,r로 지정해서
중간 지점부터 탐색을 하여 비교한다
nums = [9,7,6,3,4,2,1} 를 예로 들면
mid는 3이 될 것이고 mid가 옆에 있는 숫자보다 작으면 그 옆의 숫자부터 탐색을 시작하므로 시작점(l)이 mid+1이 되는 것이고
만약에 mid가 옆에 숫자보다 크면 오른쪽에 있는 값들은 탐색할 필요가 없으므로 끝점(r)이 mid가 되는 것이다
Runtime: 71 ms, faster than 33.75% of Python3 online submissions for Find Peak Element.
Memory Usage: 13.9 MB, less than 83.38% of Python3 online submissions for Find Peak Element.
22.06.25 복습 완
사실 이전에 벨로그에 쓴 글을 참고하고 풀이 방법을 떠올렸다..
더 연습해보아야겠다
