JavaScript로 배열에서 다음으로 큰 요소까지의 거리 구하기

문제 정의

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

이 함수는 입력 배열을 바탕으로 새로운 배열을 생성해야 합니다. 새 배열의 각 요소는 현재 요소보다 오른쪽에 있는 '다음으로 큰 요소'까지의 거리(인덱스 차이)를 의미합니다. 만약 현재 요소의 오른쪽에 더 큰 요소가 존재하지 않는다면, 해당 위치에는 0을 넣고 최종적으로 이 배열을 반환하면 됩니다.

예를 들어 함수의 입력이 다음과 같다고 가정해 보겠습니다.

입력

const arr = [12, 13, 14, 11, 16, 10, 12, 17, 19, 18];

출력

const output = [1, 1, 2, 1, 3, 1, 1, 1, 0, 0];

출력 설명

12보다 다음으로 큰 요소는 13이며, 1칸 떨어져 있습니다.

13보다 다음으로 큰 요소는 14이며, 역시 1칸 떨어져 있습니다.

14보다 다음으로 큰 요소는 16이며, 2칸 떨어져 있습니다. 이후 요소들도 같은 방식으로 계산됩니다.

접근 방식: 단조 스택(Monotonic Stack)

각 요소마다 오른쪽을 일일이 탐색하는 브루트 포스 방식은 O(n²)의 시간 복잡도를 가지므로 비효율적입니다. 대신 스택을 활용하면 O(n) 시간 안에 문제를 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

- 배열을 왼쪽부터 순회하면서 각 요소의 인덱스를 스택에 저장합니다.
- 현재 요소가 스택 맨 위 인덱스가 가리키는 값보다 크면, 해당 인덱스를 꺼내(pop) 현재 인덱스와의 거리를 결과 배열에 기록합니다.
- 순회가 끝난 후에도 스택에 남아 있는 인덱스들은 오른쪽에 더 큰 요소가 없는 경우이므로, 초기값인 0이 그대로 유지됩니다.

코드 구현

const arr = [12, 13, 14, 11, 16, 10, 12, 17, 19, 18];

const findNextGreater = (arr = []) => {
    const stack = [];
    const res = new Array(arr.length).fill(0);

    for (let i = 0; i < arr.length; i++) {
        while (stack.length > 0 && arr[i] > arr[stack[stack.length - 1]]) {
            const index = stack.pop();
            res[index] = i - index;
        }
        stack.push(i);
    }

    return res;
};

console.log(findNextGreater(arr));

실행 결과

[1, 1, 2, 1, 3, 1, 1, 1, 0, 0]

복잡도 분석

- 시간 복잡도: O(n) — 각 인덱스는 스택에 최대 한 번 push되고 한 번 pop되므로, 전체 연산 횟수는 배열 길이에 비례합니다.
- 공간 복잡도: O(n) — 스택과 결과 배열에 최대 n개의 요소가 저장될 수 있습니다.