문제83: 과반수 엘리먼트

문제

입력

[3,2,3]
[2,2,1,1,1,2,2]

출력

3,
2

풀이

1. Counter 사용

def majorityElement(self, nums):
	counts = collections.defaultdict(int)
	for num in nums:
		if counts[num] == 0:
			counts[num] = nums.count(num)
		if counts[num] > len(nums) // 2:
			return counts[nums]

1. 분할 정복

def majorityElement(self, nums):
	if not nums:
		return None
	if len(nums) == 1:
		return nums[0]

	half = len(nums) // 2
	a = self.majorityElement(nums[:half])
	b = self.majorityElement(nums[half:])
	
	return [b, a][nums.count(a) > half]

새로운 개념