[LeetCode 리트코드] 162. Find Peak Element (Java 자바)

LeetCode 리트코드 <162. Find Peak Element> 문제 보기

https://leetcode.com/problems/find-peak-element/description/?envType=study-plan-v2&envId=top-interview-150 

Find Peak Element - LeetCode

 

A peak element is an element that is strictly greater than its neighbors.

 

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

 

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

 

You must write an algorithm that runs in O(log n) time.

 

 

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.

 

Constraints:

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• nums[i] != nums[i + 1] for all valid i.

 

주어진 nums 배열 안에서 양옆의 값보다 큰 값의 index를 구하는 문제다.

nums 배열을 벗어난 범위에는 무한대로 작은 값들이 존재한다는 가정이 있다.

여러 개의 peek element 들 중 무작위의 하나만 출력하면 된다는 조건이 있다.

 

 

 

LeetCode 리트코드 <162. Find Peak Element> 문제 풀이

class Solution {
    public int findPeakElement(int[] nums) {
        int start = 0, end = nums.length-1;

        while(start<end){
            int mid = (start+end)/2;
            if(nums[mid] < nums[mid+1]) start = mid+1;
            else end = mid;
        }

        return start;
    }
}

 

 

• 접근 방식
  • 시간복잡도 제한이 O(log n) 이었기 때문에 이분탐색을 떠올릴 수 밖에 없었다.

 

• 코드 설명
  • 현재값이 오른쪽값보다 작다는 것은 무조건 오른편에 peek element가 최소 1개 존재한다는 것이다. 따라서 start 값을 mid+1로 바꿔 오른편을 탐색해줄 수 있도록 한다.
  • 만약 현재값이 오른쪽값보다 크다는 것은 현재값 혹은 왼편에 peek element가 최소 1개 존재한다는 것이다. 따라서 end 값을 mid로 바꿔 왼편을 탐색해줄 수 있도록 한다.

 

• 후기
  • 시간복잡도 제한이 없었다면 O(n)으로 풀 수 있는 간단한 문제였지만 이분탐색을 떠올려야 하는 점이 어려웠다.
  • 이분탐색을 떠올리긴 했으나 해당 알고리즘을 문제에 적용시키는 과정이 생각보다 오래 걸렸다.