[알고리즘] LeetCode - Find Peak Element

Find Peak Element - LeetCode

문제 설명

• 정수형 배열 nums가 주어진다.
• 여기서 PeekPoint (우뚝 솟아있는 부분)의 인덱스를 반환해야 한다.
• 여러 개가 있는 경우 아무거나 반환해도 상관 없다.

문제 해결

• 첫 시도에는 가장 높은 것을 반환하여 O(N) 시간 복잡도로 해결했다.
• 이분 탐색을 통해 최적화할 수 있었다.
• 정렬이 안되어 있지만, peek point인 아무 지점을 찾는 것이기 때문에 이분 탐색을 통해 최상단 지점을 아무거나 반환해도 된다.
• 이분 탐색을 통해 최댓값을 찾아가는 과정을 그대로 진행하면 해결할 수 있다.

시간 복잡도

• O(N log N)

풀이 코드

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length - 1;

        while(l < r) {
            int m = (l + r) / 2;

            if (nums[m] < nums[m + 1]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        
        return l;
    }
}

결과

시간	메모리
0 ms	41.2 MB

---

1차시도

1. 풀이 코드

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length - 1;

        while(l < r) {
            int m = (l + r) / 2;

            if (nums[m] < nums[m + 1]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        
        return l;
    }
}

2. 문제점

• O(N)의 시간 복잡도로 해결할 수 있지만 최적화가 필요하다.

3. 결과

 

2차 시도

1. 풀이 코드

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length - 1;

        while(l < r) {
            int m = (l + r) / 2;

            if (nums[m] < nums[m + 1]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        
        return l;
    }
}

2. 1차 코드 개선점

• 이분 탐색을 통해 peek point를 찾아냈다.
• 정렬되어 있지 않지만, 가장 높은 지점 중에서 아무거나 하나만 출력하면 되기 때문에 기존 이분 탐색을 통한 최댓값 도출 알고리즘을 사용하면 문제 해결이 가능했다.

3. 결과