릿코드 162. Find Peak Element 문제에 대한 복기이다.
Naive Approach
이 문제는 주어진 배열에서 왼쪽과 오른쪽 원소보다 큰 값을 가지는 "peak"를 찾아야하는 문제다.
Naive하게 접근했을때, 그냥 배열을 순회하며 각 원소가 조건에 부합하는지, O(n) 시간에 찾으면 될 것 같지만, 문제는 문제 설명 마지막에 log n 시간에 찾으라는 점이었다.
log n이라는 시간복잡도는 둘로 나눠본다는 점에서 Binary Search와 연관성이 깊다고 생각한다.
따라서 어떻게 이를 적용할지 생각하다 배열이 정렬되어 주어진것이 아니라는 것을 보고 binary search를 적용할 수 있을지 의문이 들었다.
문제에 대한 input은 다음과 같이 주어졌다. 여기서 -1 위치와 n+1위치의 가상의 원소는 -무한대라고 본다.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
문제를 풀 당시에는 무조건 한 번씩은 traverse 해야한다는 생각에 갇혀 이진탐색을 조금 더 유연하게 적용하지 못했던 것 같다. 결국 포기하고 해답을 찾아봤다.
해답
이 문제는 말 그대로 binary search를 적용하는 문제였다. 중간점을 구하고, 그 중간점이 peak인지 확인하는 것이다. Peak이 아닐 경우, 해당 중간점보다 큰 원소가 왼쪽 또는 오른쪽에 존재한다는 것이고, 중간점보다 높은 부분을 쫓아가다 보면 결론적으로 peak가 나온다는 것이다.
따라서, 해당 코드를 구현했다.
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
l = 1
r = len(nums)
if r == 1:
return 0
changed_nums = [-(2**31)] + nums +[-(2**31)]
while (l <= r):
m = (l + r) // 2
if changed_nums[m] > changed_nums[m-1] and changed_nums[m] > changed_nums[m+1]:
return (m - 1)
elif changed_nums[m] < changed_nums[m-1]:
r = m - 1
else:
l = m + 1
배운점
개인적으로 너무 쉽게 포기하고 해답을 봤다. 이진탐색을 조건의 부합하는 수 구하기, 또는 정렬된 배열에서 특정 값의 원소 찾기 등의 문제는 풀어봤지만 이런 문제는 새로운 방식이었던것 같다.
이진 탐색의 유연성에 대해 조금은 더 배운것 같다.
