Boyer-Moore 과반수 투표 알고리즘

April 13, 2023

5min read

Overview

Boyer-Moore 과반수 투표 알고리즘(Boyer-Moore Majority Vote Algorithm)은 1차원 배열에 과반수를 차지하는 배열요소가 있는지 찾는 알고리즘입니다.
1차원 배열에 과반수 요소를 찾는 문제는 공간복잡도에 제약이 없다면 Hash 자료구조를 사용하면 되므로 쉽게 $O(n)$ 의 시간복잡도로 찾을 수 있습니다. 문제는 Worst Case라면 $O(n)$ 의 메모리가 더 필요하게 되는데요, Boyer-Moore의 과반수 투표 알고리즘을 이용하면 추가 메모리 공간 없이 $O(n)$ 시간으로 해결할 수 있습니다.
이렇게 추가적인 메모리 공간을 최소화하면서 $O(n)$ 시간복잡도로 으로 문제를 해결하는 종류의 알고리즘을 Streaming Algorithm이라고 합니다. 일반적으로 Streaming Algorithm에서는 추가 메모리 공간에 제약(보통 $O({log}^{\rm c} n)$ )을 둔다고 합니다.

Boyer-Moore 과반수 투표 알고리즘

상황

예시와 함께 과반수 요소를 찾는 과정을 보겠습니다. $n$ 명의 친구가 여름에 휴가를 가려고 하는데, 휴가지는 투표로 결정됩니다. 투표 결과 과반수인 휴가지가 있을 때 그곳으로 휴가를 가기로 했습니다. 이 때, 친구들은 각자 원하는 휴가지를 딱 하나씩만 뽑아야 합니다.
예를 들어, 21명의 친구들이 투표 했을 때 부산 11표, 강릉 5표, 대전 2표, 대구 3표가 나왔다고 하면, 총 투표 용지 수는 21이고 11표는 과반수이므로 부산이 투표지로 결정되는 것입니다.
과정

이 알고리즘에서 중요한 것은 투표 결과의 기록 방식입니다. 투표 결과를 기록하면서 과반수를 찾아나가기 때문입니다.
처음 투표용지를 뽑았을 때 나온 휴가지를 과반수라고 정의하겠습니다. 이 용지를 major라고 하겠습니다. 이제 다음 투표용지의 경우의 수에 따라 아래와 같은 방식으로 처리합니다.
- major와 같은 투표용지가 나오면 major의 투표 수를 1만큼 증가시킵니다.
- major와 다른 투표용지가 나오면 major의 투표 수를 1만큼 감소시킵니다.
- major와 다른 투표용지인데 major 값이 0이면, major의 내용을 새 용지의 값으로 바꿉니다.
예를 들어, 방금 상황에서 부산 3표가 나온 상태인데 강릉 투표지가 나오면 부산 3표, 강릉 1표로 기록하는 것이 아니라, 부산 2표로 깎는 식인겁니다. 직관적으로 생각해보면, 어차피 과반수인 투표지가 있으면 쪽수로 밀어붙이기 때문에 마지막까지 남게 됩니다.

구현 코드 (Java)

major와 count만 조건에 맞게 증감시켜주면 됩니다.

public int majorityElement(int[] nums) {
    int major = nums[0];
    int count = 1;
    for(int i=1; i<nums.length; i++) {
        int cur = nums[i];

        if(major==cur) {
            count++;
        } else if(count==0) {
            major=cur;
            count++;
        } else {
            count--;
        }
    }

    return major;
}

알고리즘의 한계

과반수를 차지하는 배열요소가 없으면, '과반수'라는 로직과는 아무 상관이 없는 배열요소, 즉 마지막에 남은 배열요소가 나오게 됩니다.

예시 문제

LeetCode의 169번 문제 해당 문제에서는 과반수를 차지하는 배열요소가 반드시 1개 존재하는 1차원 배열이 주어진다.