정의

보이어-무어 다수결 투표는 "과반(절반 초과) 원소가 존재한다면 그 값을 찾아주는" 알고리즘입니다. 핵심은 후보(candidate)와 우세도(count) 단 두 변수로, 후보와 다른 값이 나올 때마다 표를 한 장씩 상쇄시키는 것입니다.

핵심 특성

• ✓왜 과반이면 살아남나: 같은 값(+1)과 다른 값(-1)을 짝지어 상쇄해도, 과반 원소는 개수가 절반을 넘으므로 짝이 모자라 반드시 count가 양수로 남습니다.
• ✓단 한 번의 순회로 끝 - 시간 O(n)
• ✓추가 배열·해시맵 불필요 - 공간 O(1)
• ✓과반이 없을 수도 있으므로, 마지막에 후보가 정말 과반인지 한 번 더 세어 검증해야 안전합니다.

시간 복잡도