[LeetCode/Top Interview 150] [Binary Search] 162. Find Peak Element

문제 링크: https://leetcode.com/problems/find-peak-element/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

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.

전략:

꼭대기 요소는 인접한 요소들보다 큰 요소이다. 주어진 배열의 인덱스는 0부터 시작한다.
꼭대기 요소의 인덱스를 리턴해주면 된다.(여럿 존재하면 그 중 아무 요소의 인덱스 리턴)
인접한 요소들은 서로 다른 값을 가지며, 범위 바깥은 -∞의 값을 가진다.

그냥 O(n)인 답을 구하는 건 쉽지만, O(log n)이라는 시간 복잡도로 구현해야만 하는 문제이다.
그래도 일단 O(n)의 답을 구해보자.

코드 구현 O(n):

class Solution {
    public int findPeakElement(int[] nums) {
        // 1개짜리 배열이면 즉시 0리턴
        if (nums.length == 1) { return 0; }

        // 최대값 찾기
        int max = Integer.MIN_VALUE;
        int pos = -1;
        // 배열 요소 수의 절반만큼의 횟수 반복
        for (int i=0;i<nums.length/2+1;i++) {            
            // 1번 반복 시 2개 요소 확인
            if (2*i<nums.length && max<nums[2*i]) {
                max=nums[2*i];
                pos=2*i;
                }
            if (2*i+1<nums.length && max<nums[2*i+1]) {
                max=nums[2*i+1];
                pos=2*i+1;
                }
        }
        return pos;
    }
}
Time: 0 ms (100%), Space: 41.2 MB (52.07%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0148-sort-list/0148-sort-list.java

일단 통과를 하기는 했는데, logn이 아니다. 다시 풀자.

O (log n):

class Solution {
    public int findPeakElement(int[] nums) {
        int start = 0, end = nums.length-1, mid = 0;
        // 1개짜리 배열이면 즉시 리턴
        if (nums.length == 1) { return 0; }

        // 이진 탐색 시 mid 위치의 값을 기준으로 Peak 가능성 체크 후 가능한 쪽 탐색
        while (start < end) {
            mid = (start + end) / 2; // 중간 위치
            if (nums[mid]<nums[mid+1]) { // 중간이 자기 옆 칸보다 작다면 -> 중간은 피크 가능성 없음
                start = mid+1; // 범위 시작을 중간 옆칸으로
            } else { // 중간이 자기 옆칸 이상이라면
                end = mid; // 끝을 중간 자리로
            }
        } 
        // 탈출 시점에서 start == end
        return end;
    }
}
Time: 0 ms (100%), Space: 40.8 MB (94.16%) - LeetHub

정렬되지 않은 배열이기에 중간값과 그 바로 다음 값의 비교만으로 탐색할 범위를 좁혀나간다.

Solutions 탭의 타인 코드:

class Solution {
    public int findPeakElement(int[] num) {    
    	// 재귀로 이진탐색
        return helper(num,0,num.length-1);
    }

    public int helper(int[] num,int start,int end){
    	// 범위가 1개의 요소로 좁혀진 경우 = 정답
        if(start == end){
            return start;
        }else if(start+1 == end){ // 범위가 2개로 좁혀진 경우
            if(num[start] > num[end]) return start; // 둘 중 더 큰 값 리턴
            return end;
        }else{
            // 진행중인 경우
            // 중간 위치
            int m = (start+end)/2;
            
            if(num[m] > num[m-1] && num[m] > num[m+1]){ // 중간 위치가 피크면
				// 중간위치 리턴
                return m;

            }else if(num[m-1] > num[m] && num[m] > num[m+1]){
				// 왼쪽이 가장 큰 요소면 왼쪽 범위 탐색
                return helper(num,start,m-1);

            }else{
				// 그 외에는 오른쪽 범위 탐색
                return helper(num,m+1,end);

            }
            
        }
    }
}
Time: 0 ms (100%), Space: 41.3 MB (52.07%) - LeetHub

회고:

그래도 역시 이진탐색은 정렬된 배열에 하는 게 더 상쾌하고, 이해가 잘 되는 해법인 거 같다.