배열 속 어떤 숫자가 자신보다 오른쪽에 있는 모든 요소보다 클 때, 그런 요소들만 골라내야 하는 경우가 있습니다. 이번 글에서는 JavaScript 함수를 작성해 원본 배열에서 이 조건을 만족하는 요소들만 담은 새 배열을 반환하는 방법을 알아보겠습니다.
문제 정의
예를 들어 다음과 같은 배열이 있다고 가정해 보겠습니다.
const arr = [12, 45, 6, 4, 23, 23, 21, 1];
이 배열에서 각 요소를 기준으로 오른쪽에 있는 모든 값과 비교할 때, 자신보다 큰 값이 하나도 없는 요소만 추출하면 됩니다. 위 배열의 경우 결과는 [1, 21, 23, 45]가 됩니다. 마지막 요소인 1은 오른쪽에 아무것도 없으므로 항상 조건을 만족한다는 점에 유의하세요.
reduceRight()를 활용한 해결 방법
가장 효율적인 접근 방식은 배열을 오른쪽에서 왼쪽으로 순회하면서 지금까지 본 최댓값을 추적하는 것입니다. JavaScript의 reduceRight() 메서드를 사용하면 이 로직을 깔끔하게 구현할 수 있습니다.
const arr = [12, 45, 6, 4, 23, 23, 21, 1];
const largerThanRight = (arr = []) => {
const creds = arr.reduceRight((acc, val) => {
let { largest, res } = acc;
if(val > largest){
res.push(val);
largest = val;
};
return { largest, res };
}, {
largest: -Infinity,
res: []
});
return creds.res;
};
console.log(largerThanRight(arr));
출력 결과
코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
[ 1, 21, 23, 45 ]
동작 원리 살펴보기
이 코드의 핵심 로직은 다음과 같습니다.
1. 초기값 설정: 누적 객체(accumulator)에 최댓값을 나타내는 largest와 결과를 담을 res 배열을 초기화합니다. 초기 최댓값은 -Infinity로 설정하여 어떤 숫자와 비교해도 첫 번째 요소가 항상 선택되도록 합니다.
2. 오른쪽부터 순회: reduceRight()는 배열의 마지막 요소부터 시작해 첫 번째 요소까지 역순으로 순회합니다. 따라서 각 단계에서 현재 값 val은 그 오른쪽에 있는 모든 요소들과 이미 비교된 상태입니다.
3. 조건 판별: 현재 값이 지금까지의 최댓값보다 크면, 해당 값은 오른쪽의 모든 요소보다 크다는 의미이므로 결과 배열에 추가하고 최댓값을 갱신합니다.
4. 결과 반환: 순회가 끝나면 결과 배열에는 조건을 만족하는 요소들이 저장되어 있으며, 이를 그대로 반환합니다.
시간 복잡도
이 방법은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 단순히 각 요소마다 오른쪽 전체를 비교하는 브루트 포스 방식(O(n²))보다 훨씬 효율적이며, 특히 대용량 배열을 처리할 때 그 차이가 두드러집니다.