JavaScript로 원형 배열에서 다음 큰 요소 찾는 방법

원형 배열(Circular Array)이란?

배열의 마지막 요소 다음에 다시 첫 번째 요소가 오는 구조를 가진 배열을 흔히 '원형 배열(circular array)'이라고 부릅니다.

물론 실제로 데이터를 이런 방식으로 저장하는 메커니즘이 존재하지는 않습니다. 데이터는 여전히 연속된 메모리 블록에 저장되며, 원형 배열은 현실적인 저장 방식이라기보다는 일종의 개념적 아이디어에 가깝습니다.

문제 정의

정수로 이루어진 원형 배열 arr를 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 원본 배열의 각 요소에 대응하는 '다음 큰 요소(Next Greater Element)'를 담은 배열을 만들어 반환해야 합니다. 어떤 숫자 num의 '다음 큰 숫자'란, 배열을 탐색 순서(여기서는 오른쪽 방향)로 진행했을 때 처음으로 마주치는 더 큰 숫자를 의미합니다. 배열이 원형이므로 끝에 도달하면 다시 처음부터 순환하며 검색할 수 있습니다. 만약 더 큰 요소가 존재하지 않는다면 해당 위치에는 -1을 넣습니다.

입력 예시

const arr = [7, 8, 7];

출력 예시

const output = [8, -1, 8];

출력 설명

배열 안의 두 개의 7 각각에 대해 다음 큰 요소는 8입니다. 배열이 원형이기 때문에 맨 뒤의 7도 앞쪽을 순환하여 8을 찾을 수 있습니다. 반면 8보다 큰 요소는 어디에도 없으므로 8의 자리에는 -1이 들어갑니다.

구현 코드

const arr = [7, 8, 7];
const nextGreaterElement = (arr = []) => {
    const res = [];
    const stack = [];
    if (!arr || arr.length < 1){
        return res;
    };
    for (let i = 0; i < arr.length; i++) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
            const small = stack.pop();
            res[small] = arr[i];
        };
        stack.push(i);
    }
    for (let i = 0; i < arr.length; i++) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
            const small = stack.pop();
            res[small] = arr[i];
        };
    }
    const rem = stack.length;
    for (let i = 0; i < rem; i++) {
        res[stack.pop()] = -1;
    }
    return res;
};
console.log(nextGreaterElement(arr));

코드 설명

이 알고리즘의 핵심은 스택(stack)을 활용한 효율적인 탐색입니다.

첫 번째 반복문에서 배열을 순회하면서, 스택의 맨 위에 있는 인덱스에 해당하는 값보다 현재 요소가 더 크면 스택에서 꺼내(pop) 해당 결과 위치 res[small]에 현재의 더 큰 값을 기록합니다. 그렇지 않으면 현재 인덱스를 스택에 push하여 나중에 처리할 후보로 남겨둡니다.

첫 번째 순회에서 다음 큰 요소를 찾지 못한 요소들을 위해, 두 번째 반복문에서 배열의 처음부터 다시 순회합니다. 이 과정 덕분에 배열이 원형처럼 동작하게 되어, 뒤쪽 요소들이 앞쪽의 더 큰 요소를 찾을 수 있습니다.

마지막으로 두 번의 순회를 거친 후에도 스택에 남아 있는 인덱스들은 배열 전체에서 자신보다 큰 요소가 존재하지 않는 것들이므로, 해당 위치에는 모두 -1을 할당합니다.

실행 결과

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

[8, -1, 8]