자바스크립트로 배열에서 리더(Leader) 요소 찾는 방법

리더(Leader) 요소란 무엇일까요?

숫자 배열에서 어떤 요소가 오른쪽에 있는 모든 요소보다 클 때, 그 요소를 '리더(Leader)'라고 부릅니다. 이번 글에서는 숫자 배열을 입력받아 리더 조건을 충족하는 모든 요소들로 이루어진 하위 배열을 반환하는 자바스크립트 함수를 작성해 보겠습니다.

예를 들어 다음과 같은 입력 배열이 있다고 가정해 보겠습니다.

[23, 55, 2, 56, 3, 6, 7, 1]

이 경우 기대하는 출력 결과는 다음과 같습니다.

[56, 7, 1]

그 이유는 다음과 같습니다. 56은 오른쪽의 모든 요소(3, 6, 7, 1)보다 크고, 7은 오른쪽의 유일한 요소인 1보다 크며, 마지막 요소인 1은 오른쪽에 비교할 대상이 없으므로 항상 리더가 됩니다. 반면 23과 55는 각각 오른쪽에 더 큰 값(56)이 존재하기 때문에 리더가 아닙니다.

reduceRight()를 활용한 해결 방법

이 문제는 배열의 오른쪽 끝부터 순회하면서 지금까지 확인한 값 중 최댓값을 계속 추적하는 방식으로 효율적으로 해결할 수 있습니다. 자바스크립트의 reduceRight() 메서드를 사용하면 이 로직을 간결하게 구현할 수 있습니다.

예제 코드

const arr = [23, 55, 2, 56, 3, 6, 7, 1];

const leaderArray = arr => {
    const creds = arr.reduceRight((acc, val) => {
        let { max, res } = acc;
        if (val > max) {
            res.unshift(val);
            max = val;
        }
        return { max, res };
    }, {
        max: -Infinity,
        res: []
    });
    return creds.res;
};

console.log(leaderArray(arr));

코드 동작 원리

• reduceRight(): 일반적인 reduce()와 달리 배열을 오른쪽(마지막 요소)에서 왼쪽(첫 번째 요소)으로 순회합니다.
• max: 초기값은 -Infinity이며, 순회 과정에서 지금까지 확인한 요소 중 최댓값을 저장합니다.
• res: 리더 요소를 담는 결과 배열입니다. 현재 값이 max보다 크면 unshift()로 배열의 맨 앞에 추가하기 때문에 최종 결과가 원래 배열의 순서를 그대로 유지하게 됩니다.

이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)으로 매우 효율적입니다.

출력 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

[56, 7, 1]