JavaScript로 중앙 피크 배열의 정점 인덱스 찾기

중앙 피크(Centrally Peaked) 배열이란?

배열 arr가 다음 두 가지 성질을 만족할 때, 우리는 이 배열을 중앙 피크 배열이라고 부릅니다.

• arr.length >= 3

• 0 < i < arr.length - 1을 만족하는 어떤 지점 i가 존재하며,

  • arr[0] < arr[1] < ... < arr[i-1] < arr[i]

  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

쉽게 말해, 배열이 어느 한 지점까지는 오름차순으로 증가하다가 그 지점부터 끝까지는 내림차순으로 감소하는 형태입니다. 마치 산맥처럼 가운데에 봉우리가 하나 솟아 있는 모양새라고 생각하면 이해하기 쉽습니다.

문제 정의

숫자 배열 arr를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

입력 배열은 항상 중앙 피크 배열이라고 가정하며, 함수는 이 배열의 피크(정점) 인덱스를 반환해야 합니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

입력

const arr = [4, 6, 8, 12, 15, 11, 7, 4, 1];

출력

const output = 4;

출력 설명

배열은 인덱스 4까지 값이 계속 증가하다가(4 → 6 → 8 → 12 → 15), 그 이후부터는 감소합니다. 따라서 인덱스 4에 위치한 요소 15가 이 배열의 피크 요소입니다.

풀이 코드

다음은 이진 탐색(Binary Search)을 활용한 해결 코드입니다. 매 단계마다 탐색 범위를 절반으로 줄여 나가기 때문에 선형 탐색(O(n))보다 훨씬 효율적인 O(log n)의 시간 복잡도로 동작합니다.

const arr = [4, 6, 8, 12, 15, 11, 7, 4, 1];
const findPeak = (arr = []) => {
    if(arr.length < 3) {
        return -1
    }
    const helper = (low, high) => {
        if(low > high) {
            return -1
        }
        const middle = Math.floor((low + high) / 2)
        if(arr[middle] <= arr[middle + 1]) {
            return helper(middle + 1, high)
        }
        if(arr[middle] <= arr[middle - 1]) {
            return helper(low, middle - 1)
        }
        return middle
    }
    return helper(0, arr.length - 1)
};
console.log(findPeak(arr));

동작 원리

이 알고리즘은 다음과 같은 방식으로 작동합니다.

• 현재 탐색 범위의 중간 인덱스 middle을 구합니다.
• arr[middle]이 오른쪽 이웃보다 작거나 같다면, 피크는 반드시 오른쪽 절반에 존재하므로 탐색 범위를 오른쪽으로 좁힙니다.
• arr[middle]이 왼쪽 이웃보다 작거나 같다면, 피크는 왼쪽 절반에 존재하므로 탐색 범위를 왼쪽으로 좁힙니다.
• 두 조건 모두 해당하지 않는다면, 현재 middle이 양쪽 이웃보다 큰 피크 지점이므로 해당 인덱스를 그대로 반환합니다.

또한 배열의 길이가 3 미만인 경우에는 중앙 피크 배열의 정의 자체가 성립할 수 없으므로, 함수 시작 시 -1을 반환하여 유효하지 않은 입력을 처리합니다.

실행 결과

4