숫자 배열을 입력받아, 자신보다 오른쪽에 있는 모든 요소보다 큰 값들만 모은 새로운 하위 배열을 반환하는 JavaScript 함수를 작성해 보겠습니다.
예를 들어 [12, 45, 6, 4, 23, 23, 21, 1]이라는 배열이 있다면, 각 요소 기준으로 오른쪽의 모든 값과 비교했을 때 더 큰 요소들만 결과에 포함됩니다.
구현 방법
이 문제는 배열의 오른쪽 끝에서부터 왼쪽으로 순회하면서 지금까지 등장한 최댓값을 추적하면 효율적으로 해결할 수 있습니다. 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. 초기값 설정: reduceRight()의 초기 누적값으로 최댓값을 나타내는 largest: -Infinity와 결과를 담을 빈 배열 res: []를 지정합니다. -Infinity를 사용하면 어떤 숫자와 비교해도 첫 번째 요소가 항상 조건을 통과합니다.
2. 오른쪽에서 왼쪽으로 순회: reduceRight()는 일반적인 reduce()와 달리 배열의 마지막 요소부터 첫 번째 요소까지 순회합니다. 덕분에 각 요소를 처리하는 시점에는 그 오른쪽에 있는 모든 요소들이 이미 검사된 상태입니다.
3. 조건 판별: 현재 값 val이 지금까지 발견한 최댓값 largest보다 크면, 현재 값은 오른쪽의 모든 요소보다 크다는 의미이므로 결과 배열에 추가하고 최댓값을 갱신합니다.
4. 결과 반환: 순회가 끝나면 조건을 만족한 요소들만 담긴 배열이 반환됩니다.
결과 배열인 [1, 21, 23, 45]를 보면, 각 요소가 실제로 자신의 오른쪽에 있는 모든 값보다 크거나 같은 위치에 있음을 확인할 수 있습니다. 예를 들어 45는 맨 뒤에 있는 어떤 값보다도 크고, 1은 배열의 마지막 요소이므로 비교 대상이 없어 항상 포함됩니다.
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도가 O(n)으로 매우 효율적입니다.