Majority Vote Algorithm

보이어 무어 과반수 투표 알고리즘

정의

배열 상에서 과반수 출현하는 패턴을 찾기 위한 알고리즘.

시간 복잡도: O(N), 공간 복잡도: O(1)

N개의 정수 Array에서 과반수(N/2)번보다 많이 출현하는 정수를 찾기.

컨셉

Majority Element의 출현 횟수 > 다른 Elements들의 출현 횟수

위 전제조건을 만족하는 상황에서 배열을 처음부터 순회할 때, 순회하는 각 시점기준으로 가장 많이 출현한 Majority Element와 그 횟수를 기록해둔다. 가장 마지막까지 순회했을 때, 기록되어있는 Majority Element가 배열에서 과반수로 나온 정수임을 알 수 있다.

(단, 위 조건을 만족하지 않는 경우 값을 찾을 수 없다.)

로직

• majority, appear_count 변수 선언

  • majority : 과반수로 많이 출현한 정수
  • appear_count : majority의 출현 횟수

• 배열 순회 (N번째 element까지 각 element를 e 라고 호칭)

• majority와 e가 같은가?

  • 같다 : appear_count 1 증가
  • 다르다 : appear_count 1 감소

• appear_count가 음수라면?

  • majority를 e로 변경
  • appear_count를 1로 변경

구현

추후 예정

참고 자료

• MinJunKweon 개발 블로그