문제 설명

LeetCode 162번 문제인 "피크 요소 찾기"를 해결하는 방법에 대해 알아보겠습니다. 이 문제에서는 주어진 배열에서 피크 요소(즉, 그 이웃보다 큰 요소)를 찾아야 합니다.

해결 전략

• 배열의 인접한 요소들은 서로 같지 않으며, 피크는 여러 개 존재할 수 있습니다. 전체 배열의 최댓값은 항상 피크 중 하나입니다. 따라서 단순히 배열을 순회하며 최댓값을 찾으면 답을 얻을 수 있지만, 문제는 O(log n) 시간 복잡도를 요구합니다.
• 이를 만족하려면 이진 탐색 알고리즘을 사용해야 합니다.
• 문제 조건상 배열의 끝부분은 마치 음의 무한대와 연결되어 있다고 간주됩니다. 이를 통해 첫 번째 요소와 마지막 요소가 피크인지 확인할 수 있습니다.
• 만약 첫 번째 또는 마지막 요소가 피크가 아니라면, 배열의 처음은 오름차순이고 끝은 내림차순으로 변하는 구간이 존재하며, 이 사이 어딘가에 피크가 반드시 존재합니다.
• 세 연속된 요소를 비교하여 피크 여부를 판단할 수 있습니다:

1. data[i - 1] < data[i] > data[i + 1]: i는 피크입니다.
2. data[i - 1] < data[i] < data[i + 1]: i는 아직 상승 추세에 있으므로, i 이후의 부분에서 계속 검색합니다.
3. data[i - 1] > data[i] > data[i + 1]: i는 하강 추세에 있으며, i 이전의 부분에서 피크를 찾습니다.
4. data[i - 1] > data[i] < data[i + 1]: i는 계곡점이며, 좌우 어느 쪽에도 피크가 존재할 가능성이 있습니다.

• 위 경우들을 종합하면, data[i] > data[i + 1]일 때는 현재 위치(i) 혹은 그 왼쪽에서 피크를 찾고, data[i] < data[i + 1]일 때는 오른쪽에서 피크를 찾을 수 있습니다.

코드 예시

다음은 이해하기 쉬운 버전의 코드입니다:

public int findPeakElement(int[] data) {
    if (data.length == 1 || data[0] > data[1]) {
        return 0;
    }
    int end = data.length - 1;
    if (data[end] > data[end - 1]) {
        return end;
    }
    int start = 0;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (mid < data.length - 1 && data[mid] > data[mid + 1]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return start;
}

더 간단한 버전의 코드도 아래와 같습니다:

public int findPeakElement(int[] data) {
    int left = 0, right = data.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (data[mid] < data[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}