보이어-무어 다수결 투표 (Boyer-Moore Majority Vote)

정의

보이어-무어 다수결 투표 (Boyer-Moore Majority Vote) 는 배열에서 과반수 (> N/2) 를 차지하는 원소를 O(N) 시간, O(1) 공간으로 찾는 알고리즘. 1982년 Robert S. Boyer와 J Strother Moore가 고안.

문제 상황과 동기

배열 a[0..N-1] 에서 과반수 원소 (N/2 번 이상 나타나는 원소) 를 찾는다.

• naive: 각 원소마다 등장 횟수 세기. O(N^2) 또는 hash map 으로 O(N) 시간, O(N) 공간.
• 핵심 통찰: 서로 다른 두 원소를 짝지으면 둘 다 제거해도 과반수는 변하지 않음. 이를 반복하면 마지막에 남은 원소가 유일한 후보.

자주 등장: 투표 시스템, 센서 데이터 이상 탐지, 스트림 처리.

시각화

핵심 아이디어

Invariant: (candidate, count) 쌍을 유지. count 가 0이면 현재 원소를 새 후보로, 같으면 count++, 다르면 count—.

핵심: 과반수 원소 x 가 존재하면, 다른 모든 원소를 제거해도 x 는 남음.
      count 가 0 이 되는 순간 새 후보를 선택해도, 
      x 의 등장 횟수 > (다른 모든 원소의 합) 이므로 x 가 최종 후보.

주의: 과반수가 존재하지 않을 수도 있으므로 두 번째 pass 에서 검증 필수.

알고리즘

majority_vote(a[0..N-1]):
    # Pass 1: 후보 찾기
    candidate = null
    count = 0
    for i = 0..N-1:
        if count == 0:
            candidate = a[i]
            count = 1
        else if a[i] == candidate:
            count += 1
        else:
            count -= 1
    
    # Pass 2: 검증 (과반수 확인)
    count = 0
    for i = 0..N-1:
        if a[i] == candidate:
            count += 1
    
    if count > N / 2:
        return candidate
    else:
        return -1  # 과반수 없음

구현

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  
  // Pass 1: 후보 찾기
  int candidate = -1, count = 0;
  for (int i = 0; i < n; i++) {
      if (count == 0) {
          candidate = a[i];
          count = 1;
      } else if (a[i] == candidate) {
          count++;
      } else {
          count--;
      }
  }
  
  // Pass 2: 검증
  count = 0;
  for (int i = 0; i < n; i++) {
      if (a[i] == candidate) count++;
  }
  
  if (count > n / 2) {
      cout << candidate << "\n";
  } else {
      cout << -1 << "\n";
  }
  return 0;
}

n = int(input())
a = list(map(int, input().split()))
​
# Pass 1: 후보 찾기
candidate = None
count = 0
for x in a:
  if count == 0:
      candidate = x
      count = 1
  elif x == candidate:
      count += 1
  else:
      count -= 1
​
# Pass 2: 검증
count = a.count(candidate)
if count > n // 2:
  print(candidate)
else:
  print(-1)

import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      int[] a = new int[n];
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) {
          a[i] = Integer.parseInt(st.nextToken());
      }
      
      // Pass 1: 후보 찾기
      int candidate = -1, count = 0;
      for (int i = 0; i < n; i++) {
          if (count == 0) {
              candidate = a[i];
              count = 1;
          } else if (a[i] == candidate) {
              count++;
          } else {
              count--;
          }
      }
      
      // Pass 2: 검증
      count = 0;
      for (int i = 0; i < n; i++) {
          if (a[i] == candidate) count++;
      }
      
      if (count > n / 2) {
          System.out.println(candidate);
      } else {
          System.out.println(-1);
      }
  }
}

7
2 3 2 1 2 4 2

2

4
1 2 3 4

-1

복잡도

변형 / 활용

1. 모든 과반수 원소 찾기 (k-majority)

N/k 이상 등장하는 모든 원소 찾기. 최대 k-1 개 후보 유지.

2. 스트림 처리

배열 전체를 메모리에 올릴 수 없을 때, 한 번에 한 원소씩 처리 가능.

3. 분산 환경

각 노드에서 로컬 후보 찾고, 전역 후보 검증.

함정

1. 검증 pass 필수

과반수가 존재하지 않으면 candidate 는 의미 없음. 반드시 두 번째 pass 에서 count > N/2 확인.

2. > N/2 vs >= N/2

알고리즘은 strictly greater than N/2 만 보장. >= N/2 를 원하면 다른 접근 필요.

3. 음수 / 큰 수

hash map 대신 쓰는 이유가 O(1) 공간이므로, 음수나 큰 수도 그대로 처리 가능. 단, 정수 범위 주의.

BOJ 연습 문제

참고

• 해시셋
• 정렬