JavaScript로 배열에서 가장 긴 산(Mountain) 부분 배열 찾기

산(Mountain) 부분 수열이란?

배열 arr의 연속된 부분 배열 sub가 다음 두 조건을 모두 만족할 때, 이를 '산(mountain)'이라고 정의합니다.

부분 배열의 길이가 3 이상입니다. (sub.length >= 3)
0 < i < sub.length - 1인 인덱스 i가 존재하여, sub[0] < sub[1] < ... < sub[i] > sub[i+1] > ... > sub[sub.length - 1]을 만족합니다. 즉, 특정 지점(정상)까지는 엄격하게 증가하고, 그 이후부터는 엄격하게 감소하는 형태여야 합니다.

문제 설명

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

함수는 배열 arr 안에 존재하는 가장 긴 산 부분 수열의 길이를 반환해야 하며, 산 형태의 부분 배열이 하나도 없다면 0을 반환합니다.

입력 예시

const arr = [3, 2, 5, 8, 4, 3, 6];

출력 예시

const output = 5;

출력 설명

가장 긴 산 부분 배열은 다음과 같습니다.

[2, 5, 8, 4, 3]

이 배열은 2 → 5 → 8로 증가한 뒤, 8 → 4 → 3으로 감소하기 때문에 유효한 산입니다. 길이는 5입니다.

구현 코드

다음은 투 포인터(two pointer) 방식으로 문제를 해결한 코드입니다.

const arr = [3, 2, 5, 8, 4, 3, 6];
const mountainLength = (arr = []) => {
    let max = 0;
    for(let left = 0; left < arr.length; left++) {
        // 1단계: 왼쪽에서 시작해 증가 구간의 끝(정상)을 찾습니다.
        let right = left;
        while(arr[right] < arr[right + 1]) {
            right++;
        }
        const top = right;
        // 2단계: 정상 이후 감소 구간의 끝을 찾습니다.
        while(right > left && arr[right] > arr[right + 1]) {
            right++;
        }
        // 3단계: 실제로 증가와 감소가 모두 일어났는지 확인합니다.
        if(right > top && top > left) {
            max = Math.max(max, right - left + 1);
            left = right;
            left--;
        }
    }
    return max;
};
console.log(mountainLength(arr));

코드 동작 원리

이 알고리즘은 다음과 같은 단계로 동작합니다.

증가 구간 탐색: left 포인터에서 시작해 arr[right] < arr[right + 1]인 동안 right를 앞으로 이동시켜 증가 구간의 끝, 즉 산의 정상(top)을 찾습니다.
감소 구간 탐색: 정상 이후에는 arr[right] > arr[right + 1]인 동안 right를 계속 이동시켜 감소 구간의 끝을 찾습니다.
유효성 검사 및 최대값 갱신: right > top && top > left 조건은 증가 구간과 감소 구간이 실제로 모두 존재했음을 의미합니다. 조건을 만족하면 현재 산의 길이(right - left + 1)로 최대값을 갱신하고, left를 right로 옮겨 중복 탐색을 줄입니다.

이 방식은 각 요소를 상수 번씩만 방문하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

실행 결과

배열 [3, 2, 5, 8, 4, 3, 6]에서 가장 긴 산 부분 배열은 [2, 5, 8, 4, 3]이며, 그 길이인 5가 출력됩니다.