보이어 무어의 과반수 투표 알고리즘(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 = {}..