JavaScript로 정렬된 배열에서 과반수 요소(Majority Element) 판별하는 방법

과반수 요소(Majority Element)란?

길이가 l인 배열 arr에서 과반수 요소(majority element)란 배열 전체 길이의 절반(l / 2)보다 더 많은 횟수로 등장하는 요소를 말합니다. 따라서 이러한 요소는 배열 안에 최대 한 개만 존재할 수 있습니다.

이번 글에서는 JavaScript 함수 isMajority()를 작성해 보겠습니다. 이 함수는 다음과 같은 인자를 받습니다.

첫 번째 인자: 항상 오름차순으로 정렬되어 있는 배열 arr
두 번째 인자: 배열에서 찾고자 하는 숫자

함수는 두 번째 인자로 받은 숫자가 과반수 요소라면 true, 아니라면 false를 반환합니다.

입력 예시

const arr = [5, 5, 5, 12, 15];
const num = 5;

출력 결과

const output = true;

배열 [5, 5, 5, 12, 15]에서 숫자 5는 총 3번 등장하며, 이는 배열 길이의 절반인 (5 / 2) = 2.5보다 크기 때문에 5는 과반수 요소입니다.

핵심 아이디어: 정렬된 배열의 중간 값 활용

문제 해결의 열쇠는 배열이 이미 정렬되어 있다는 조건입니다. 만약 과반수 요소가 존재한다면, 그 숫자는 배열의 절반 이상을 차지해야 하므로 반드시 중간(middle) 위치의 요소가 될 수밖에 없습니다.

즉, 복잡한 순회나 카운팅 없이도 다음과 같은 간단한 논리로 판별할 수 있습니다.

배열 길이의 절반 위치(중간 인덱스)를 구합니다.
해당 위치의 값이 찾고자 하는 숫자와 일치하는지 비교합니다.
일치하면 true, 그렇지 않으면 false를 반환합니다.

구현 코드

위 로직을 코드로 구현하면 다음과 같습니다.

const arr = [5, 5, 5, 12, 15];
const num = 5;

const isMajority = (arr = [], num = 1) => {
    const { length } = arr;
    if (!length) {
        return false;
    }
    
    const middle = Math.floor(length / 2);
    
    if (arr[middle] === num) {
        return true;
    } else {
        return false;
    }
};

console.log(isMajority(arr, num));

실행 결과

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

true

정리

이 방법의 가장 큰 장점은 시간 복잡도가 O(1)이라는 점입니다. 배열 전체를 탐색하지 않고 중간 요소 한 번만 확인하기 때문에 매우 효율적입니다. 단, 이 접근 방식은 배열이 반드시 정렬되어 있어야 한다는 전제 조건이 필요합니다. 정렬되지 않은 배열이라면 먼저 정렬(O(n log n))을 수행하거나, 보이어-무어(Boyer-Moore) 과반수 투표 알고리즘 같은 대안을 고려해야 합니다.