[Leetcode Top Interview 150] 162. Find Peak Element

난이도 : medium

문제링크

• peak element : 이웃보다 큰 노드
• peak element의 인덱스를 리턴하라
• peak element는 복수개가 될 수 있으나, 어느것중 하나만 정확하게 리턴하라
• 시간복잡도 O(logn) 성능의 알고리즘을 작성하라
• 1 <= nums.length <= 1000
• nums[i] != nums[i+1]

 

1. 접근법

• O(logn)의 성능이 필요하므로 Binary Search가 적절함
• 또한, 배열에서 이웃중에서 큰 값은 배열 전체에서 가장 큰 원소를 찾는것과 같음

 

2. 의사코드

while (right < left) {
	mid = (right+left)/2+1;
    if (nums[mid] > nums[mid-1]) {
    	left = mid;
    } else {
        right = mid-1;
    }
}

return right

 

3. 구현 코드

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        
        while (right > left) {
            mid = (right + left)/2 + 1;
            if (nums[mid] > nums[mid-1]) {
                left = mid;
            } else {
                right = mid-1;
            }
        }
        
        return right;
    }
}

• 투포인터를 두고, 각 포인터의 중간값과 중간값의 직전값을 비교함
• 중간값이 크다면, 가장 큰 값의 인덱스 범위는 mid ~ right 안에 있으므로 left를 mid로 변경
• 중간값의 직전값이 크다면, 가장 큰 값의 인덱스 범위는 left ~ mid-1 안에 있으므로 right를 mid-1로 변경
• right가 left보다 작을때까지 수행하므로 마지막으로 반복문을 돌았던 상태에서 right가 가장 큰 값의 인덱스값이 됨

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(logn) - 반복문을 돌때마다 범위가 반씩 줄어듬
• 공간복잡도 : O(1) - 상수 크기만 사용함

 

5. 개선점

• 잘 모르겠다