leetcode easy : Majority Element (얕보면 큰일나는 문제)

https://leetcode.com/problems/majority-element/description/

Majority Element - LeetCode

 

EASY길래 가벼운 마음으로 문제를 봤다가 당혹감을 감출수없었다.

Follow-up 조건 때문이었다.

살짝 그 스멜이 났다. 웰노운 알고리즘의 스멜 ^~^

비슷한 문제로 https://leetcode.com/problems/maximum-subarray/ 가 있다. 근데 이거 원래 EASY였는데 어느샌가 MEDIUM으로 바뀌었네..ㅋㅋㅋ EASY하지 않긴 했어~~

 

잘 생각해보면 majority element는 반드시 n/2번을 초과해서 등장한다.

이상이 아니다. 초과다. N이 5면 3개 이상 등장하고

N이 7이면 4개 이상 등장하고..

무조건 절반보다 많다.

이말이 무슨말이냐면

서로 다른 숫자를 짝지어서 쌍소멸 시키는 상상을 해보면 결국에 남는 요소가 majority element가 된다는 것이다.

쌍소멸 시킨다는 상상을 하면 되게 쉽게 이해되고 쉽게 풀린다.

 

class Solution:
    # O(N) Time, O(1) Space required
    def majorityElement(self, nums: List[int]) -> int:
        """
        Simple Fact
        * majority element랑 아닌 요소를 하나씩 쌍소멸시키면 majority element가 한 개 이상 남는다.
        
        즉 서로 다른 요소를 쌍소멸시키는걸 반복하면 결국 majority element만 살아남는다.
        """

        element = nums[0]
        frequency = 1
        
        i = 1
        while i < len(nums):
            if frequency == 0:
                element = nums[i]
                frequency = 1
                i += 1
                continue
            if nums[i] == element:
                frequency += 1
            else:
                frequency -= 1
            i += 1

        return element