쉬움
Majority Element
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 다수원소(nums):2 후보 = 없음, 표 = 03 반복 i = 0 … n-1:4 만약 표 = 0: 후보 = nums[i]5 만약 nums[i] = 후보: 표 += 16 아니면: 표 -= 1 // 다른 값과 상쇄7 반환 후보
변수
- i
- 0
- nums[i]
- 3
- 후보
- 3
- 표
- 1
1 / 4표가 0이라 3 을(를) 새 후보로 삼고 표를 1 로 시작합니다.
과반 원소는 다른 값들과 하나씩 상쇄돼도 반드시 살아남는다 — 후보와 표 하나로 찾는다(Boyer-Moore).
왜 헷갈리는가
해시맵으로 개수를 세면 쉽지만 O(n) 공간이 든다. Boyer-Moore는 O(1) 공간으로 끝나는데, '왜 상쇄 후에도 다수가 남는지'가 직관적으로 안 와닿는다.
핵심 아이디어
다수 원소가 절반을 넘으므로, 서로 다른 값끼리 1:1로 지워도 다수 원소가 마지막까지 남는다. 표가 0이 되면 후보를 새로 잡는다.
복잡도
시간 O(n)·공간 O(1). 해시맵 풀이(O(n) 공간)보다 메모리가 낫다. (과반 보장이 없으면 2차 검증 필요.)
실무에서 어디에 쓰나
'스트림에서 지배적 값'을 메모리 없이 추정하는 계열의 원형이다.
- 합의/투표: 리더 선출·과반 판정의 단순 모델
- 스트림 분석: 대용량 로그에서 지배적 값 근사(heavy hitters의 기초)
- 센서 융합: 다수결로 이상치 제거(fault-tolerant voting)
- 네트워크: 패킷 스트림의 최빈 항목 저메모리 추정
흔한 실수
과반이 보장되지 않는 입력에 그대로 쓰기(그땐 2차 카운트로 확인). 표 0일 때 후보 교체를 빼먹기.
기억할 것
- 과반은 상쇄에도 살아남는다.
- O(1) 공간이 핵심.
- heavy-hitters·투표의 원형.
- 과반 미보장이면 2차 검증.