Boyer-Moore Voting Algorithm / 과반수 투표 알고리즘

[수정] 내용에 오류가 있어 글을 수정했습니다. 지적해 주신 피곤한투티님 감사합니다.

---

과반수 투표 알고리즘이란 주어진 배열 내에서 과반 수 이상을 차지하는 요소가 존재하는지의 여부와 그 요소를 찾아내는 알고리즘입니다.

과반수를 찾아내기 위해 자주 사용되는 방식으로는 2중 반복문을 사용하거나, hash를 활용하는 방법이 있습니다.

하지만 두 방식을 사용하는 것보다 더욱 효율적으로 과반수를 찾아내는 방식이 과반수 투표 알고리즘입니다.

 

코드를 통해 살펴보겠습니다.

int majorityElement(vector<int>& nums) {
        int cnt = 0;
        int candidate;
        
        for(int i = 0; i < nums.size(); i++) {
            if(cnt == 0) {
                candidate = nums[i];
            }
            cnt += (candidate == nums[i]) ? 1 : -1;
        }
        
        float majorCount = 7/2.0f;
        for(int i = 0; i < nums.size(); i++) {
        	if(nums[i] == candidate) {
        		majorCount --;
        	}
        	if(majorCount <= 0) {
        		return candidate;
        	}
        }
        return -1;
    }

 

과반수 투표 알고리즘은 과반 수 이상을 차지하는 요소는 다른 요소들로 인해 상쇄될 수 없다는 점을 이용합니다.

 

예제 코드를 보면 알 수 있듯이

같은 수가 연속해서 나온다면 cnt에 1을 더해주고

다른 수가 나온다면 cnt에 1을 빼줍니다.

 

만약 cnt가 0이 된다면 비교할 후보를 새로운 대상으로 바꿔줍니다.

 

위 과정을 을 통해 과반수일 확률이 있는 후보를 선정할 수 있습니다.

 

이후 한번 더 반복문을 실행시켜 후보가 과반수가 맞는지 확인해 준다.

 

만일 후보가 과반수 이상을 차지할 경우 후보를 반환해 주며,
과반수가 아닐 경우 -1을 반환한다.

과반수 투표 알고리즘을 사용할 경우

이중 반복문을 사용하는 방식보다 빠르게 연산 가능하며, hash를 사용하는 방식보다 메모리를 적게 사용할 수 있습니다.

 

# Time complexity : O(n)

# Space complexity : O(1)

 

참고

en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

Boyer–Moore majority vote algorithm - Wikipedia