[Leetcode][Python] 229. Majority Element II

리트코드 / 파이썬 / 229.Majority Element II

leetcode.com/problems/majority-element-ii/

Majority Element II - LeetCode

풀이 방법

처음에 생각한 방법은 dictionary(hashmap)으로 number 별 count 수를 늘리는 방법,

그리고 O(nlogn)으로 정렬한 후 한 번 순회하며 count를 더해나가는 방법이었다.

 

하지만 문제에서는 time O(n), space O(1)의 방법으로 풀 것을 제시하고 있다.

 

time O(n), space O(1)를 위해서는 'Boyer-Moore Majority Vote algorithm'으로 풀어야 한다. 

 

Boyer-Moore Majority Vote algorithm

leetcode.com/problems/majority-element-ii/discuss/63520/boyer-moore-majority-vote-algorithm-and-my-elaboration/64978

Boyer-Moore Majority Vote algorithm and my elaboration - LeetCode Discuss

릿코드의 discussion을 참고했다.

 

우선 문제에서는 n//3개 이상 출현한 num을 구하는 것인데, 답은 최대 2개까지 나올 수 있다는 것을 유추할 수 있다.

즉, 정답이 될 수 있는 candidate은 2개다.

 

Boyer-Moore의 설명을 읽는 것 보다 아래와 같이 예시를 본 후에 설명을 읽는 것이 훨씬 이해가 잘되었다.
댓글에서는 1,2,3,4,5,6으로 예시를 들었는데, 그것보다는 기존 문제 예시인 1,1,1,3,3,2,2,2가 이해하기 쉽다.

 

아래는 1,1,1,3,3,2,2,2 예시를 Boyer-Moore Majority Vote algorithm을 이용하여 표로 나타낸 것이다.

 

looping through the list	candidate1, count	candidate2, count	description
1	1 (cnt: 1)
1,1	1 (cnt: 2)
1,1,1	1 (cnt: 3)
1,1,1,3	1 (cnt: 3)	3 (cnt: 1)
1,1,1,3,3	1 (cnt: 3)	3 (cnt: 2)
1,1,1,3,3,2	1 (cnt: 2)	3 (cnt: 1)	1, 3, 2 pair -> 각각 count -= 1
1,1,1,3,3,2,2	1 (cnt: 1)	3 (cnt: 0)	1, 3, 2 pair -> 각각 count -= 1
1,1,1,3,3,2,2,2	1 (cnt: 0)	2 (cnt: 1)	candidate2 cnt = 0, 신규 num 2 추가

위의 표에서 보는 것과 같이, list를 순회하면서 특정 숫자가 반복되는 경우 count를 1씩 늘려주고,

candidate1, candidate2가 각각 존재하는 상황에서 새로운 숫자가 들어오는 경우 candidate1, 2의 count를 각각 1씩 빼준다. 

 

새로운 숫자가 들어오는 경우, 왜 기존 candidate1, 2의 count를 1씩 빼줘야할까?

count를 각각 -1씩 빼주는 것의 의미는 pair가 완성되었다는 뜻이다.

아래의 예시에서 빨간색으로 표시한 것은, 위의 표에서 빨간색으로 표시한 부분과 같다. 

 

1  | 3 | 2 -> 1, 3의 count -= 1

1  | 3 | 2 -> 1, 3의 count -= 1

1  |    | 2 -> 3은 count = 0 이므로, 3의 자리에 2 신규 진입

 

count는 list상에서의 빈도수를 의미하지는 않는다.

따라서, candidate으로 남은 두 숫자(1, 2)를 list에서 다시 한 번 순회하여 빈도수가 n//3를 넘는지 확인해야 한다.

 

복잡도는 list를 세 번 순회하므로 O(3n), 즉 O(n)이다.

 

소스 코드

class Solution(object):
    def majorityElement(self, nums):
        """
        https://leetcode.com/problems/majority-element-ii/
        :type nums: List[int]
        :rtype: List[int]
        """
        candidate1, candidate2 = 0, 1
        cnt1 = cnt2 = 0
        result = list()

        for num in nums:
            if candidate1 == num:
                cnt1 += 1
            elif candidate2 == num:
                cnt2 += 1
            elif cnt1 == 0:
                candidate1 = num
                cnt1 = 1
            elif cnt2 == 0:
                candidate2 = num
                cnt2 = 1
            else:
                cnt1 -= 1
                cnt2 -= 1

        if len([num for num in nums if num == candidate1]) > len(nums) // 3:
            result.append(candidate1)
        if len([num for num in nums if num == candidate2]) > len(nums) // 3:
            result.append(candidate2)

        return result