자바스크립트로 배열에 과반수 요소가 존재하는지 확인하는 방법

숫자로 이루어진 배열이 주어졌을 때, 특정 요소가 배열 전체 길이의 절반보다 많은 횟수로 등장한다면 그 요소를 과반수(majority) 요소라고 부릅니다.

과반수 요소란?

예를 들어 배열의 길이가 7이라면, 어떤 요소가 최소 4번 이상 등장할 때 그 요소를 과반수 요소로 간주합니다. 직관적으로 생각해볼 때, 하나의 배열에는 최대 한 개의 과반수 요소만 존재할 수 있습니다.

우리는 반복되는 값을 가진 숫자 배열을 인자로 받아, 배열 안에 과반수 요소가 존재하면 true, 존재하지 않으면 false를 반환하는 자바스크립트 함수를 작성해야 합니다.

구현 예제

다음은 위 로직을 구현한 코드입니다.

const arr = [12, 5, 67, 12, 4, 12, 4, 12, 6, 12, 12];
const isMajority = arr => {
    let maxChar = -Infinity, maxCount = 1;
    // 첫 번째 루프: 과반수 요소의 후보를 결정합니다
    for(let i = 0; i < arr.length; i++){
        if(maxChar !== arr[i]){
            if(maxCount === 1){
                maxChar = arr[i];
            }else{
                maxCount--;
            };
        }else{
            maxCount++;
        };
    };
    // 두 번째 루프: 후보가 실제로 과반수 요소인지 검증합니다
    const count = arr.reduce((acc, val) => maxChar===val ? ++acc : acc, 0);
    return count > arr.length / 2;
};
console.log(isMajority(arr));

출력 결과

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

true

코드 동작 원리

이 알고리즘은 보이어-무어投票(Boyer-Moore Voting) 알고리즘을 기반으로 하며, 두 단계로 나뉩니다.

1단계 — 후보 선정: 배열을 순회하면서 현재 후보와 같은 값이 나오면 카운트를 증가시키고, 다른 값이 나오면 감소시킵니다. 카운트가 0이 되면 새로운 후보를 지정합니다. 이 과정이 끝나면 실제 과반수 요소가 존재한다면 반드시 그 요소가 후보로 남게 됩니다.

2단계 — 후보 검증: 선정된 후보가 실제로 배열 길이의 절반을 초과하는 횟수로 등장하는지 reduce()를 통해 개수를 세어 확인합니다. 이 검증 단계가 필요한 이유는, 과반수 요소가 없는 경우에도 1단계에서 임의의 후보가 남을 수 있기 때문입니다.

이 방식은 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적이며, 객체나 맵을 사용해 빈도를 세는 방식(O(n) 공간)보다 메모리 측면에서 유리합니다.