보이어 무어의 과반수 투표 알고리즘(Boyer-Moore Majority Vote Algorithm)

크기 n인 배열에 있는 원소들 중에서, 개수가 n//2 + 1개 이상인 원소가 하나 존재한다고 하자.

 

즉, 절반을 넘는 개수를 가진 원소가 무조건 하나가 있을때 이 원소를 찾고 싶다.

 

어떻게 찾을 수 있을까?

 

예를 들어 [2,2,1,3,2,2]에서 2는 개수가 4개있고 크기 6인 배열에서 이것이 과반수 이상의 원소이다.

 

가장 쉬운 방법은 O(N)으로 배열을 순회해서 각 원소의 개수를 모두 찾아 hash에 저장해둔다.

 

이 hash에서 가장 원소의 개수가 많은 원소를 찾으면 된다.

 

이러면 시간복잡도 O(N)에 공간복잡도 O(N)에 찾을 수 있다.

 

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        
        h = {}

        for i in range(len(nums)):

            h[nums[i]] = h.get(nums[i],0) + 1
        
        max_c = 0
        max_v = -1

        for c in h:

            if max_c < h[c]:

                max_c = h[c]
                max_v = c
        
        return max_v

 

 

근데 만약에 시간복잡도 O(N) 그리고 공간복잡도 O(1)에 해결하라고 하면?

 

위 솔루션에서는 hash를 선언하여 공간복잡도 O(N)이 되었다.

 

즉 배열이나 hash 등을 선언하지 말고 기본 변수만으로 이 문제를 해결해야한다면?

 

그럴때 사용하는 알고리즘이 Boyer-Moore Majority Vote Algorithm이다.

 

빈 경기장이 있다고 상상해보자.

 

배열을 차례대로 순회하면서 원소 하나씩 빈 경기장에 출전한다.

 

이때 count를 선언하고 이는 경기장 위에 있는 원소의 개수이다.

 

이때 경기장 위에 있는 원소와 새로 출전한 원소가 서로 같다면? 세력을 키워나가서 count + 1해주고

 

경기장 위에 있는 원소와 새로 출전한 원소가 서로 다르다면 새로 출전한 원소가 경기장 위에 있는 세력 하나를 제거한다.

 

그래서 count - 1을 해준다.

 

만약 현재 count가 0이하가 된다면? 현재 출전한 원소가 새롭게 경기장 위에 서서 대장이 된다.

 

모든 원소를 순회했을때, 현재 대장이 문제에서 요구하는 과반수 이상의 원소가 된다.

 

이렇게 풀면 count, v변수만 선언했으므로 공간복잡도가 O(1)이다.

 

class Solution:
    def majorityElement(self, nums: List[int]) -> int:

        count = 1
        v = nums[0]
        
        for i in range(1,len(nums)):

            if nums[i] == v:

                count += 1
            
            else:

                count -= 1

                if count == 0:

                    v = nums[i]
                    count = 1
        
        return v