[Leetcode] Peak Index in a Mountain Array

문제 출처

• https://leetcode.com/problems/peak-index-in-a-mountain-array/

Peak Index in a Mountain Array - LeetCode

 

문제 해설

• 주어진 배열(arr)에서 산봉우리에 위치하는 인덱스를 구하는 문제
• 산봉우리가 위치한 인덱스를 i라고 할 때, 산봉우리를 만족하는 조건으로는
  
  1. arr[0] < arr[1] < ... < arr[i]
  2. arr[-1] < arr[-2] < ... < arr[i]
• 결론적으로 보면 산봉우리는 배열에서 가장 큰 값이며, 그 값의 위치를 찾아내면 될 것이다.

 

문제 풀이

# source: https://leetcode.com/problems/peak-index-in-a-mountain-array/?envType=study-plan&id=binary-search-i


class Solution:
    def peakIndexInMountainArray(self, arr: list[int]) -> int:
        start = 0
        end = len(arr) - 1

        max_value = -1
        max_index = -1
        while start <= end:
            point1 = arr[start]
            point2 = arr[end]

            if point1 >= point2:
                end -= 1
                if point1 > max_value:
                    max_value = point1
                    max_index = start
            else:
                start += 1
                if point2 > max_value:
                    max_value = point2
                    max_index = end

        return max_index

 

• 형태는 이진 탐색처럼 작성하였고 배열의 맨 왼쪽 값과 오른쪽 값에서부터 시작해 최댓값을 구하도록 작성

 

Github

• https://github.com/limseunghyun95/Algorithm_study/blob/master/leetcode/peak_index_in_a_mountain_array.py