Algorithm: 과반수 찾기

Brute Force Method

• 자신보다 뒤에 나오는 수 가 자신과 같다면 카운팅 해가며 찾는방법
• O(n^2)

O(n log n) 방법

• 원소들을 정렬한다 (O(n log n) 의 시간)
  • 정렬전: 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2
  • 정렬후: 1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3
• 등장 횟수를 검사하는데에 O(n)의 시간
• 전체 시간: O(n log n)

O(n) 방법: Boyer-Moore

다음과 같이 작동한다: 같은 수라면 skip, 다른 수라면 상쇄

• 다음 숫자열에 대해 작동 과정을 살펴보자
• 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2
  • 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2 (상쇄)
  • 2 2 1 1 1 1 2 1 3 2 1 1 1 2 (skip)
  • 2 2 1 1 1 1 2 1 3 2 1 1 1 2 (상쇄)
  • 2 1 1 1 2 1 3 2 1 1 1 2
  • 1 1 2 1 3 2 1 1 1 2
  • 1 1 2 1 3 2 1 1 1 2
  • 1 1 3 2 1 1 1 2
  • 1 1 3 2 1 1 1 2
  • 1 2 1 1 1 2
  • 1 1 1 2
  • 1 1 1 2
  • 1 1 1 2
  • 1 1
  • 1 1 1 9 9 9 2 1 2 1 1
• 증명
  • 과반수인 원소가 x 라고 하자. 위 방법을 사용해 왼쪽 한 그룹을 제거하더라도 남은 원소 중 과반수인 원소는 x
  • 첫 원소는 둘중 하나: x 이거나 x가 아니거나.
    • x 라면 x 가 나온 횟수만큼 다른 원소들이 맨 왼쪽 한 그룹에 포함
    • 같은 횟수만큼 x와 다른 원소가 제거되므로 남은 원소 중 과반수 이상이 x
    • 만약 x 가 첫 원소가 아니더라도 여전히 남은 원소 중 과반수 이상이 x
  • 만약 절반 이상으로 나오는 값이 있다면 가장 오른쪽 그룹의 맨 앞의 값이다.
    • 과반수 원소가 m 이라고 하고 각 원소마다 자신이 m 이면 카운터를 +1 아니면 -1 
    • 과반수가 있다면 카운터 값은 1 이상