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--;
}