[LeetCode] 162. Find Peak Element

🎨 문제

peak은 산의 정상을 의미한다. 배열이 주어지는데 값이 증가하다가 감소하는 포인트가 있다. 이를 peak라 부르며 해당 위치를 찾는 문제이다. peak은 여러 개 존재할 수 있으며 이 중 아무 위치나 리턴하면 된다. 양 끝 값의 경우 0번 째 이전(-1번째)와 마지막 다음 번째(n번째)의 값을 -∞로 하여 0번째와 n-1 번째도 peak이 될 수 있다. 그림으로 보면 이해하기 쉬울 것이다.

L과 R도 peak이 될 수 있다. 

Find Peak Element - LeetCode

📘 풀이

peak을 찾아야 하므로 peak을 기준으로 mid의 위치에 따라 케이스를 분류해 보자. 세 가지 케이스가 나올 수 있다.

case

1. peak < mid

2. mid == peak

3. mid < peak

mid의 위치에 따른 세 가지 case

peak의 위치는 아직 모르므로 case를 다음과 같이 다시 쓸 수 있다.

 

1. nums[mid] < nums[mid + 1]

2. nums[mid - 1] < nums[mid] < nums[mid + 1]

3. nums[mid] < nums[mid - 1]

 

peak이 존재하는 곳으로 탐색 범위를 좁혀야 한다. 이를 바탕으로 코드를 작성하면 다음과 같다.

public int findPeakElement(int[] nums) {
        if (nums.length == 1) return 0;

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

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

        return -1;      // dummy
    }

하지만 이 코드는 문제가 있다. nums[0]과 nums[nums.length - 1]가 peak일 경우를 고려하지 않았다.

양 끝점 고려

1. 0번째가 peak일 경우 ➡ nums[0] > nums[1]

2. n번째가 peak일 경우 ➡ nums[n - 1] < nums[n]

 

해당 부분을 고려하여 코드를 작성하면

public int findPeakElement(int[] nums) {
        if (nums.length == 1) return 0;

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) >>> 1;

            if (mid == 0) {
                if (nums[mid] > nums[mid + 1]) return mid;
                else left = mid + 1;
                continue;
            } else if (mid == nums.length - 1) {
                if (nums[mid] > nums[mid - 1]) return mid;
                else right = mid - 1;
                continue;
            }

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

        return -1;      // dummy
    }