Boyer moore majority vote algorithm 보이어무어 과반수 투표 알고리즘
Boyer moore majority vote algorithm 보이어무어 과반수 투표 알고리즘
- 배열에서 과반수를 차지하는 숫자를 시간복잡도 O(n), 공간복잡도 O(1) 에 찾을 수 있는 알고리즘
- 항상 과반수가 존재 할 때 성립하는 알고리즘임
int candidate = nums[0];
int count = 1;
for(int i = 1; i < nums.size(); ++i) {
if(count == 0) candidate = nums[i];
if(candidate == nums[i]) count++;
else count--;
}
return candidate;
1. 과반수가 될 후보를 골라낸다. 처음은 nums[0];
2. 반복문을 돌며 과반수가 맞는지 확인하는 과정을 거친다.
2-1. 과반수에 해당하는 숫자가 없다면 현재 숫자를 과반수 후보로 지정
2-2. 현재 숫자가 과반수 후보와 같다면 갯수를 1 증가 시킨다.
2-3. 과반수 후보와 다르다면 1을 감소 시킨다.
-------------------------------------------------------------------
| 1 | 3 | 1 | 3 | 3 | 4 | 3 | 4 | 3 | 3 |
---------
candidate = 1;
count = 1;
| count = 1; candidate = 1 count--; count -> 0 |
|||||||||
| 1 | 3 | 1 | 3 | 3 | 4 | 3 | 4 | 3 | 3 |
count = 0;
candidate = 1
-------------------------------------------------------------------
| count = 0 candidate = 1; count++; count -> 1 |
|||||||||
| 1 | 3 | 1 | 3 | 3 | 4 | 3 | 4 | 3 | 3 |
count = 1;
candidate = 1
-------------------------------------------------------------------
| count = 1; candidate = 1; count--; count -> 0 |
|||||||||
| 1 | 3 | 1 | 3 | 3 | 4 | 3 | 4 | 3 | 3 |
count = 0;
candidate = 1;
-------------------------------------------------------------------
| count = 0; candidate = 1 ----- -> candidate = 3; count++; count -> 1 |
|||||||||
| 1 | 3 | 1 | 3 | 3 | 4 | 3 | 4 | 3 | 3 |
count = 1;
candidate = 3
-------------------------------------------------------------------
| count = 1 candidate = 3; count++; count -> 2 |
|||||||||
| 1 | 3 | 1 | 3 | 3 | 4 | 3 | 4 | 3 | 3 |
count = 2;
candidate = 3;
-------------------------------------------------------------------
| count = 2; candidate = 3; count--; count -> 1 |
|||||||||
| 1 | 3 | 1 | 3 | 3 | 4 | 3 | 4 | 3 | 3 |
count = 1;
candidate = 3;
-------------------------------------------------------------------
| count = 1; candidate = 3; count++; count -> 2 |
|||||||||
| 1 | 3 | 1 | 3 | 3 | 4 | 3 | 4 | 3 | 3 |
count = 2;
candidate = 3;
-------------------------------------------------------------------
| count = 2; candidate = 3; count--; count -> 1 |
|||||||||
| 1 | 3 | 1 | 3 | 3 | 4 | 3 | 4 | 3 | 3 |
count = 1;
candidate = 3;
-------------------------------------------------------------------
| count = 1; candidate = 3; count++; count -> 2 |
|||||||||
| 1 | 3 | 1 | 3 | 3 | 4 | 3 | 4 | 3 | 3 |
count = 2;
candidate = 3;
-------------------------------------------------------------------
| count = 2; candidate = 3; count++; count -> 3 |
|||||||||
| 1 | 3 | 1 | 3 | 3 | 4 | 3 | 4 | 3 | 3 |
count = 3;
candidate = 3;
Result = 3;
여기서 이 알고리즘이 성립하기 위한 조건은 이것이다.
배열에서 과반수 이상을 차지하는 숫자가 "무조건" 존재한다
무조건 과반수 이상인 숫자가 존재하기 때문에 해당 이후에 나오는 후보 숫자가 교체 된 후에 나온 수가 과반수에 해당하는 숫자라고 보장 할 수 있는것
여기서 드는 의문점!
그럼 딱 절반은? -> 절반은 안됨!
[1, 1, 1, 2, 3, 3]
[2, 1, 1, 3, 3, 1]
이렇게 2개의 배열이 있다고 하자. 절반에 해당하는 수는 1
[1,1,1,2,3,3] 일 때 해당 알고리즘을 적용하면
1 이 나오지만
[2, 1, 1, 3, 3, 1]
의 배열에선 3이 나온다.
int count = 0;
int candidate = 0;
for(int i : nums) {
if(count == 0) candidate = i;
if(candidate == i) count++;
else count--;
}