JavaScript 배열에서 세 번째 최댓값 찾기

문제 개요

숫자 배열을 첫 번째이자 유일한 인수로 받아 처리하는 JavaScript 함수를 작성해야 합니다.

함수의 핵심 임무는 배열에서 세 번째로 큰 수(세 번째 최댓값)를 찾아 반환하는 것입니다. 만약 배열에 서로 다른 값이 3개 미만으로 존재하여 세 번째 최댓값이 없다면, 배열의 최댓값을 대신 반환하면 됩니다.

문제 이해하기

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

const arr = [34, 67, 31, 87, 12, 30, 22];

이 배열의 고유한 값들을 내림차순으로 정렬하면 87, 67, 34, 31, 30, 22, 12 순서가 되므로, 세 번째 최댓값은 34입니다. 따라서 출력은 다음과 같아야 합니다.

const output = 34;

구현 코드

const arr = [34, 67, 31, 87, 12, 30, 22];
const findThirdMax = (arr = []) => {
    const map = {};
    let j = 0;
    for (let i = 0, l = arr.length; i < l; i++) {
        if(!map[arr[i]]){
            map[arr[i]] = true;
        }else{
            continue;
        };
        arr[j++] = arr[i];
    };
    arr.length = j;
    let result = -Infinity;
    if (j < 3) {
        for (let i = 0; i < j; ++i) {
            result = Math.max(result, arr[i]);
        }
        return result;
    } else {
        arr.sort(function (prev, next) {
            if (next >= prev) return -1;
            return 1;
        });
        return arr[j - 3]
    };
};
console.log(findThirdMax(arr));

코드 동작 원리

위 코드의 로직을 단계별로 살펴보면 다음과 같습니다.

중복 제거: map 객체를 해시 테이블처럼 활용해 이미 등장한 숫자를 기록하고, 중복된 값은 건너뜁니다. 이 과정에서 중복이 제거된 요소들은 배열 앞쪽으로 재배치되며, 마지막에 arr.length = j로 배열 길이를 조정합니다.
고유 값이 3개 미만인 경우: 세 번째 최댓값이 존재하지 않으므로, Math.max()를 사용해 배열 전체의 최댓값을 계산해 반환합니다.
고유 값이 3개 이상인 경우: 배열을 오름차순으로 정렬한 뒤, 뒤에서 세 번째 위치(arr[j - 3])에 있는 값을 반환합니다. 이것이 곧 세 번째 최댓값입니다.

참고: 이 방식은 정렬 단계 때문에 평균적으로 O(n log n)의 시간 복잡도를 가집니다. 최댓값, 두 번째 최댓값, 세 번째 최댓값을 담을 변수 세 개만 유지하면서 배열을 한 번만 순회하면 O(n) 시간에 해결할 수 있는 최적화도 가능합니다.

실행 결과

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