숫자로 이루어진 배열을 인자로 받아, 그중 세 번째로 큰 숫자를 찾아 반환하는 JavaScript 함수를 작성해 보겠습니다.
이 문제의 핵심 조건은 함수의 시간 복잡도가 O(n)을 초과해서는 안 된다는 것입니다. 즉, 정렬 없이 배열을 단 한 번만 순회하면서 세 번째 최댓값을 찾아내야 합니다.
접근 방식
핵심 아이디어는 최댓값(first), 두 번째 값(second), 세 번째 값(third)을 저장할 변수 세 개를 준비하는 것입니다. 처음에는 세 변수를 모두 -Infinity로 초기화한 뒤, 배열의 각 요소를 순회하면서 값의 크기를 비교해 적절한 자리에 배치하고 나머지 값을 한 칸씩 뒤로 밀어냅니다.
또한 중복된 값은 continue로 건너뛰도록 처리하여, 서로 다른(distinct) 값 기준으로 세 번째로 큰 수를 구할 수 있습니다. 만약 배열에 서로 다른 숫자가 3개 미만이라면 세 번째 값이 존재하지 않으므로, 그 경우에는 최댓값을 대신 반환하도록 했습니다.
예제 코드
const arr = [1, 5, 23, 3, 676, 4, 35, 4, 2];
const findThirdMax = (arr) => {
let [first, second, third] = [-Infinity, -Infinity, -Infinity];
for (let el of arr) {
if (el === first || el === second || el === third) {
continue;
}
if (el > first) {
[first, second, third] = [el, first, second];
continue;
}
if (el > second) {
[second, third] = [el, second];
continue;
}
if (el > third) {
third = el;
continue;
}
}
return third !== -Infinity ? third : first;
};
console.log(findThirdMax(arr));출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
23
코드 동작 원리
위 코드가 어떻게 작동하는지 단계별로 살펴보겠습니다.
- 중복 값 건너뛰기: 현재 요소가 이미 first, second, third 중 하나와 같다면 계산에서 제외합니다. 덕분에 중복 값이 세 번째 최댓값 판정에 영향을 주지 않습니다.
- 새로운 최댓값 발견 시: 요소가 first보다 크면 기존 값들을 한 칸씩 뒤로 밀어냅니다(first → second → third).
- 두 번째 자리에 삽입될 때: 요소가 second보다 크다면 second와 third를 한 칸씩 뒤로 밀어냅니다.
- 세 번째 값 갱신: 요소가 third보다 크다면 third 값만 새로 갱신합니다.
- 예외 처리: 순회가 끝난 후에도 third가 여전히
-Infinity라면(즉, 서로 다른 수가 3개 미만이라면) 최댓값인 first를 반환합니다.
예제 배열 [1, 5, 23, 3, 676, 4, 35, 4, 2]에서 가장 큰 수는 676, 두 번째는 35, 세 번째는 23입니다. 따라서 위 함수는 23을 정확하게 반환합니다.