JavaScript 배열에서 두 번째로 많이 등장하는 요소 찾기

문제 개요

리터럴 값으로 이루어진 배열을 인자로 받아, 배열 안에서 두 번째로 많이 등장하는 요소를 반환하는 JavaScript 함수를 작성해 보겠습니다.

예를 들어, 다음과 같은 배열이 입력으로 주어졌다고 가정해 봅시다.

const arr = [2, 5, 4, 3, 2, 6, 5, 5, 7, 2, 5];

이 배열에서 5는 4번, 2는 3번 등장합니다. 즉, 가장 많이 등장하는 요소는 5이고, 두 번째로 많이 등장하는 요소는 2입니다. 따라서 기대되는 출력 결과는 다음과 같습니다.

const output = 2;

해결 접근 방법

이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.

빈도수 계산 — 배열을 한 번 순회하면서 각 요소가 몇 번 등장하는지 객체(해시 맵)에 기록합니다.
정렬 후 반환 — 등장 횟수를 기준으로 키를 내림차순 정렬한 뒤, 두 번째 위치의 요소를 반환합니다.

코드 구현

const arr = [2, 5, 4, 3, 2, 6, 5, 5, 7, 2, 5];

const findSecondMost = (arr = []) => {
    const map = {};
    arr.forEach(el => {
        if (map.hasOwnProperty(el)) {
            map[el]++;
        } else {
            map[el] = 1;
        }
    });
    const sorted = Object.keys(map).sort((a, b) => map[b] - map[a]);
    return sorted[1];
};

console.log(findSecondMost(arr));

실행 결과

코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

코드 설명

findSecondMost 함수의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

먼저 빈 객체 map을 생성한 뒤, forEach로 배열의 모든 요소를 순회하며 각 값의 등장 횟수를 카운트합니다. hasOwnProperty를 사용해 해당 키가 이미 존재하는지 확인하고, 존재하면 값을 1 증가시키고, 없으면 1로 초기화합니다.
이후 Object.keys(map)으로 모든 고유 요소의 목록을 가져오고, sort에 비교 함수 (a, b) => map[b] - map[a]를 전달해 등장 횟수가 많은 순서대로 내림차순 정렬합니다.
정렬된 배열의 인덱스 0은 가장 많이 등장한 요소이므로, 인덱스 1에 해당하는 값이 곧 두 번째로 많이 등장하는 요소가 됩니다.

시간 복잡도

빈도수 계산에는 O(n), 정렬에는 O(k log k)(k는 고유 요소의 개수)가 소요되므로, 전체 시간 복잡도는 O(n + k log k)입니다. 일반적인 경우 k는 n보다 작거나 같기 때문에 효율적인 해결 방식이라고 할 수 있습니다.