LeetCode-162 Find Peak Element 파이썬 풀이

Find Peak Element - LeetCode

문제

리스트에서 피크 값을 찾는 문제입니다. 피크에 해당하는 요소의 인덱스를 반환하면 됩니다. 피크가 여러개라면 어떤 지점을 반환해도 상관 없습니다. 여기서 피크 값이란 양 옆의 숫자들보다 완벽하게 큰 숫자입니다. 시간복잡도는 O(logN)을 만족해야 합니다. 

풀이

사실 이 문제는 max를 이용해서 너무 간단하게 해결할 수 있습니다. 주어진 배열에서 max() 함수를 활용하여 가장 큰 값을 찾으면 그 값이 피크값이 될 것이고, 해당 값으로 index() 함수를 사용해 인덱스를 찾을 수 있습니다.

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        return nums.index(max(nums))
        

다른 방법으로는 이진 탐색을 활용해 해결할 수 있습니다.

1. 배열의 가장 첫번째(left)와 마지막인덱스(right)를 반으로 나누어 중간 인덱스를 구합니다.

2. 배열의 중간 인덱스 값과 가장 마지막 값을 비교했을때 중간 값이 더 작다면 중간 값의 그 다음 값을 첫번째 값(left)으로 둡니다.

3. 만약 중간값이 마지막 값보다 작거나 같다면 중간값을 마지막 값으로 저장합니다.

4. left가 right보다 작을 때까지 반복하여 가장 큰값을 구할 수 있습니다.

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1

        while(right > left):
            tmp = int((left + right) / 2)
            if (nums[tmp] < nums[tmp + 1]):
                left = tmp + 1
            else:
                right = tmp
        return right