JavaScript에서 거의 증가하는 수열(Almost Increasing Sequence) 확인하기

엄격하게 증가하는 수열이란?

수열 내 모든 요소가 바로 앞의 요소보다 클 때, 그 수열을 엄격하게 증가하는 수열(strictly increasing sequence)이라고 부릅니다. 예를 들어 [1, 3, 5]는 엄격하게 증가하는 수열이지만, [1, 3, 3]은 같은 값이 연속으로 등장하므로 해당하지 않습니다.

이번 글에서는 숫자 배열을 인수로 받아, 최대 한 개의 요소만 제거했을 때 남은 숫자들로 엄격하게 증가하는 수열을 만들 수 있는지 판별하는 JavaScript 함수를 작성해 보겠습니다.

구현 아이디어

문제 해결 과정은 다음과 같이 단순화할 수 있습니다.

1. 먼저 배열이 이미 엄격하게 증가하는 수열인지 확인합니다.
2. 그렇지 않다면, 각 위치의 요소를 하나씩 제거해 본 배열을 만듭니다.
3. 제거한 결과 중 하나라도 엄격하게 증가하는 수열이라면 true를 반환하고, 어떤 경우에도 불가능하면 false를 반환합니다.

예제 코드

다음은 전체 구현 코드입니다.

const almostIncreasingSequence = (arr = []) => {
    if (isIncreasingSequence(arr)) {
        return true;
    };
    for (let i = 0; i < arr.length > 0; i++) {
        let copy = arr.slice(0);
        copy.splice(i, 1);
        if (isIncreasingSequence(copy)) {
            return true;
        };
    };
    return false;
};
const isIncreasingSequence = (arr = []) => {
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] >= arr[i + 1]) {
            return false;
        };
    };
    return true;
};
console.log(almostIncreasingSequence([1, 3, 2, 1]));
console.log(almostIncreasingSequence([1, 3, 2]));

코드 설명

isIncreasingSequence 함수는 인접한 두 요소를 비교하여 현재 요소가 다음 요소보다 크거나 같은 경우가 있으면 false를 반환합니다. 이 조건 덕분에 같은 값이 반복되는 경우도 엄격하게 증가하는 수열에서 제외됩니다.

almostIncreasingSequence 함수는 먼저 원본 배열을 검사하고, 실패하면 slice()로 배열 복사본을 만든 뒤 splice(i, 1)로 i번째 요소를 제거하며 가능한 모든 경우를 시도합니다.

실행 결과

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

false
true

[1, 3, 2, 1]은 두 개 이상의 요소를 제거해야만 엄격하게 증가하는 수열이 되므로 false가 출력되고, [1, 3, 2]는 3 또는 2 중 하나만 제거하면 되므로 true가 출력됩니다.