Boyer-Moore Voting Algorithm을 통한 O(n) 시간 및 O(1) 공간 복잡도 달성

Context

배열 내 n/2 초과 빈도로 등장하는 Majority Element를 식별하는 문제 상황 분석. Brute Force의 시간 복잡도 과다와 HashMap의 추가 공간 비용 발생이라는 트레이드오프 존재.

Technical Solution

• Moore's Voting Algorithm 도입을 통한 공간 복잡도 최소화
• 동일 원소 발견 시 카운트를 증가시키고 다른 원소 발견 시 감소시키는 상쇄 메커니즘 설계
• 과반수 이상의 빈도를 가진 원소가 다른 모든 원소의 결합보다 많다는 수학적 성질 활용
• 단일 Pass 스캔을 통해 최종 생존 후보자를 결정하는 선형 탐색 구조 채택
• HashMap의 O(n) Space Overhead를 제거하여 메모리 효율 극대화

Impact

• 시간 복잡도: O(n²) (Brute Force) → O(n) (Moore's Voting)으로 개선
• 공간 복잡도: O(n) (HashMap) → O(1) (Moore's Voting)으로 최적화