JavaScript로 배열 내 최대 인덱스 차이(j - i) 구하기

문제 정의

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

배열 내 두 인덱스 i와 j가 다음 조건을 만족한다고 가정합니다.

• i < j, 그리고

• arr[i] <= arr[j]

이러한 조건을 만족하는 모든 인덱스 튜플 (i, j) 중에서, 함수는 j - i의 차이가 가장 큰 값을 반환해야 합니다.

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

const arr = [6, 0, 8, 2, 1, 5];

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

const output = 4;

출력 설명

최대 차이는 (i, j) = (1, 5)일 때 달성됩니다. 즉, arr[1] = 0이고 arr[5] = 5이므로 조건 arr[i] <= arr[j]를 만족하며, 이때의 차이 5 - 1 = 4가 가능한 최댓값입니다.

접근 방식: 스택 활용

이 문제는 스택을 활용하면 효율적으로 해결할 수 있습니다. 먼저 왼쪽에서 오른쪽으로 배열을 순회하면서 감소하는 값들의 인덱스만 스택에 저장합니다. 그런 다음 오른쪽에서 왼쪽으로 순회하면서, 스택에 저장된 인덱스의 값보다 현재 값이 크거나 같으면 스택에서 인덱스를 꺼내며 차이를 계산하고 최댓값을 갱신합니다. 이 방식은 시간 복잡도 O(n)으로 선형 시간 안에 해결할 수 있다는 장점이 있습니다.

예제 코드

이를 구현한 코드는 다음과 같습니다.

const arr = [6, 0, 8, 2, 1, 5];
const maximumDifference = (arr = []) => {
    let max = 0
    const stack = [0]
    for (let i = 1; i < arr.length; i++) {
       if (arr[i] < arr[stack[stack.length - 1]]) {
          stack.push(i)
       }
    }
    for (let i = arr.length - 1; i >= 0; i--) {
       while (arr[i] >= arr[stack[stack.length - 1]]) {
          max = Math.max(max, i - stack.pop())
       }
    }
    return max;
};
console.log(maximumDifference(arr));

출력 결과

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

4