162. Find Peak Element

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

문제

peak요소: 이웃 요소보다 큰 요소

배열의 peak 인덱스를 반환하자.

• O(logn) 시간 내에 실행
• 모든 i에 대해 • nums[i] != nums[i + 1] 성립

입력

• 정수 배열 nums

출력

• peak 요소의 index

---

나의 풀이

접근

실행시간이 O(logn)이 되어야 한다는 게 포인트다.

그렇다면 이진탐색 알고리즘이 O(logn) 인데 어떻게 구현할 지 고민되었다.

• 배열 순서 변경이 불가하니, 정렬을 이용하는 방법은 아닐 것
• 양쪽의 요소만 검사하면 되는데.. 탐색하며 어떻게 탐색 범위를 반씩 줄여나갈까?

이런 저런 생각을 하다가, O(n)의 실행 시간을 가지는 코드만 작성할 수 있었다. 너무 시간이 지체되어 다른 풀이를 봤다.

---

다른 풀이

이 풀이는 peak 요소의 좌측은 증가하고 있고, 우측은 감소하고 있다는 peak의 특징을 잘 이용했다.

• 먼저 엣지 케이스인 경우를 걸러내기 위해, 길이가 1인 경우와 가장 끝의 요소 검사를 진행
• start, end, mid 포인터를 사용해 이진 탐색 진행
  • 만약, mid의 오른쪽이 더 크다면 아직 peak를 향해 증가하고 있는 상태 → start를 mid보다 더 뒤로 이동
  • 만약, mid의 왼쪽이 더 크다면 peak 요소 후 감소하고 있는 상태 → end를 mid보다 앞당긴다.

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;

        // 길이가 1일 경우
        if (nums.length == 1) return 0;

        // 가장 왼쪽의 요소가 peak 인지 검사
        if (nums[0] > nums[1])
            return 0;

        // 가장 오른쪽의 요소가 peak 인지 검사
        if (nums[n - 1] > nums[n - 2])
            return n - 1;
        
        int start = 1, end = n - 2, mid = (start / end) / 2;
        while(start <= end) {
            mid = (start + end) / 2;
            if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1])
                return mid;
            else if (nums[mid] < nums[mid+1])
                start = mid+1;
            else if (nums[mid] < nums[mid-1])
                end = mid-1;
        }
        return -1;
    }
}

이제 다른 문제를 풀 때에도, 정렬을 하지 않아도 이진 탐색을 사용할 수 있다는 사실을 고려해야 한다.

또한 엣지케이스를 if문으로 따로 빼서 처리하는 알고리즘은 사실 깔끔하지 않다고 생각했었다. 따라서 되도록이면, 하나의 로직 안에서 탐색하도록 하려는 편이었는데, 이제는 그런 생각은 하지 말아야겠다.