JavaScript 배열에서 가장 큰 두 요소를 한 번의 순회로 찾는 방법

정렬되지 않은 숫자 배열이 주어졌을 때, 이 배열에서 가장 큰 두 요소(최댓값 두 개)를 추출하여 새로운 배열로 반환하는 함수를 작성하는 것이 목표입니다.

여기서 중요한 조건은 단 한 번의 순회(one pass), 즉 선형 시간(O(n)) 안에 작업을 완료해야 한다는 점입니다. for 반복문을 하나만 사용하거나, ES6 메서드를 활용할 경우에도 중첩된 호출 없이 단일 메서드만 사용하여 시간 복잡도가 증가하지 않도록 해야 합니다.

이 문제는 Array.prototype.reduce() 메서드를 활용하면 깔끔하게 해결할 수 있습니다. reduce는 배열을 한 번만 순회하면서 누적값(acc)과 현재값(val)을 비교할 수 있기 때문입니다.

핵심 로직

누적값으로 초기 배열 [-Infinity, -Infinity]를 설정하고, 각 요소를 순회하며 다음 규칙을 적용합니다.

• 현재 값이 최댓값(acc[0])보다 크면 → 기존 최댓값을 두 번째 자리로 밀어내고 현재 값을 최댓값으로 갱신합니다.
• 그렇지 않고 현재 값이 두 번째 값(acc[1])보다 크면 → 두 번째 값을 현재 값으로 갱신합니다.

예제 코드

const arr = [23, 65, 67, 23, 2, 6, 87, 23, 45, 65, 3, 234, 3];

const topTwo = arr => {
    // 요소가 2개 미만인 경우 처리 불가
    if(arr.length < 2){
        return false;
    };
    return arr.reduce((acc, val) => {
        if(val > acc[0]){
            let t = acc[0];
            acc[0] = val;
            acc[1] = t;
        } else if(val > acc[1]){
            acc[1] = val;
        };
        return acc;
    }, [-Infinity, -Infinity]);
};

console.log(topTwo(arr));

실행 결과

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

[ 234, 87 ]

배열에서 가장 큰 값인 234와 두 번째로 큰 값인 87이 올바른 순서로 반환된 것을 확인할 수 있습니다. 이 방식은 배열 전체를 딱 한 번만 순회하므로 시간 복잡도는 O(n)으로 유지되며, 추가 정렬 없이도 효율적으로 상위 두 요소를 구할 수 있습니다.