JavaScript로 중앙 정점(산 모양) 배열 확인하기

문제 소개

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

이 함수는 입력 배열이 중앙 정점 배열(centrally peaked array)인지 판별하여, 해당하면 true, 그렇지 않으면 false를 반환해야 합니다.

중앙 정점 배열의 조건

배열이 중앙 정점 배열이 되기 위해서는 다음 조건을 만족해야 합니다.

배열 길이가 3 이상이어야 합니다. (arr.length >= 3)
0 < i < arr.length - 1을 만족하는 인덱스 i가 존재해야 하며:

정점까지는 값이 계속 증가합니다: arr[0] < arr[1] < ... < arr[i]
정점 이후에는 값이 계속 감소합니다: arr[i] > arr[i+1] > ... > arr[arr.length - 1]

즉, 배열이 산처럼 한 지점에서 상승했다가 다시 하강하는 형태여야 하며, 값이 동일하게 유지되는 구간이 있어서는 안 됩니다.

예시

예를 들어 함수의 입력이 다음과 같다면,

const arr = [2, 6, 7, 9, 5, 3, 1];

출력은 다음과 같아야 합니다.

const output = true;

출력 설명

배열이 9에서 정점에 도달하기 때문입니다. 9까지는 값이 계속 증가하고, 9 이후부터는 계속 감소하므로 완벽한 산 모양 배열입니다.

구현 코드

이 문제를 해결하는 코드는 다음과 같습니다.

const arr = [2, 6, 7, 9, 5, 3, 1];

const isCentrallyPeaked = (arr = []) => {
    let ind = undefined;
    for (let i = 1; i <= arr.length - 1; i++) {
        if (ind === undefined) {
            // 아직 정점을 찾지 못한 상태
            if (arr[i] < arr[i - 1]) {
                // 감소 구간 진입 → 바로 앞 요소가 정점
                ind = i - 1;
            } else if (arr[i] === arr[i - 1]) {
                // 같은 값이 연속되면 산 모양이 아님
                return false;
            }
        } else if (arr[i] >= arr[i - 1]) {
            // 감소 중에 다시 증가하거나 같아지면 실패
            return false;
        }
    }
    // 정점이 양 끝에 위치하지 않아야 유효한 산 모양
    return ind > 0 && ind < arr.length - 1;
};

console.log(isCentrallyPeaked(arr));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true

동작 원리 정리

이 알고리즘은 배열을 단 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 핵심 로직은 다음과 같습니다.

정점 탐색: 증가 구간을 지나 처음으로 값이 감소하는 지점을 만나면, 그 앞 요소를 정점(ind)으로 기록합니다.
유효성 검사: 증가 중에 같은 값이 등장하거나, 감소 구간에서 다시 증가·동일해지는 경우 즉시 false를 반환합니다.
경계 확인: 마지막에 정점이 첫 번째 또는 마지막 인덱스에 있다면 실질적으로 단조 증가/감소 배열일 뿐이므로, ind > 0 && ind < arr.length - 1 조건으로 걸러냅니다.

이처럼 한 번의 순회와 몇 가지 조건 검사만으로 배열이 산 모양인지 효율적으로 판별할 수 있습니다.