분할 정복_Leet #169.Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

 

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

 

Constraints:

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

 

---

분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말한다.

쉽게 말해서 문제를 분할하고 정복한 다음 정답을 조합해나간다는 의미이다.

 

• 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다.
• 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
• 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

 

---

sol1. 브루트 포스

처음 봤을 때는 브루트 포스로 문제를 풀었다.

숫자를 하나씩 체크해서 그 숫자의 개수가 과반수가 넘는지 확인하다가 과반수가 넘으면 return하는 방식이다.

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

        for i in num_list:
            if nums.count(i) >= len(nums)/2:
                return i

 

 

sol2. 분할 정복

분할 정복을 공부하기 위해서 분할 정복으로 풀어보고자 하였다.

리스트를 반으로 쪼갠 다음 과반수 후보군만을 리턴하면서 백트래킹하면 최종적으로 정답이 출력된다.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        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]