[Leetcode/파이썬] 169. Majority Element

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
• The input is generated such that a majority element will exist in the array.

 

Follow-up: Could you solve the problem in linear time and in O(1) space?

 

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = 0
        for num in nums :
            if cnt == 0 :
                majority_num = num
                
            cnt += 1 if majority_num == num else -1

        return majority_num

뭔가 새로운 풀이 방법이라 문제 못 풀었음. 

nums에서 숫자 하나씩 빼와서 cnt=0이면 주요 숫자를 현재 숫자로 갱신, 이후 cnt에 1을 추가한다. 

현재 주요 숫자와 같은 숫자가 나오면 cnt에 1을 추가, 다른 숫자가 나오면 1을 차감 하는 방식으로 진행하며 만약 0이라면 주요 숫자를 교체한다. 

처음을 어떻게 할 것인가가 중요했는데 위와 같이 코드를 작성하면 처음도 무난하게 cnt = 1 로 시작할 수 있다. 신기한 접근이었다. 

그리고 마지막으로 주요 숫자를 반환하면 끝. 

풀이를 보면 쉬운데 이런 코드를 어떻게 생각해낼지에 대해서 고민을 조금 더 해봐야 할 것 같다.