[leetcode - python] Majority Element

문제 설명

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

Majority Element - LeetCode

배열 중 과반수 이상 등장하는 수를 찾는 문제

• 난이도 - Easy

---

관련 개념

Boyer-Moore Voting Algorithm (보이어-무어 과반수 투표 알고리즘)

: 인접한 두 수가 서로 다르다면 둘 다 버리는 개념의 알고리즘.

2개를 버리면 과반수가 1 줄어드므로 Majority Element에는 영향이 없다는 것을 이용.

예) 50개의 수 중 2가 25번 등장해 Majority Element일 때, 2와 3을 버려도 48개의 수 중 2가 24번 등장하므로 여전히 2가 Majority Element이다.

---

접근 방법 1. 브루트 포스

배열 원소 당 한 번 씩 배열의 모든 값들과 비교하고, 같은 값이 나오는 경우를 카운팅한다.

이 때 이미 한 번 카운팅한 수는 다시 할 필요 없으므로 예외처리를 해준다.

 

접근 방법 2. 배열 정렬

1. 배열을 정렬한다.

2. 배열을 순회하다가 다른 숫자를 만나면 카운팅을 처음부터 다시 시작한다.

3. 카운팅 횟수가 n/2 이상이 되면 해당 수를 반환한다.

 

접근 방법 3. Boyer-Moore Voting

후보값과 배열의 원소들을 비교해 같으면 카운팅을 더하고, 다르면 뺀다.

이 때 카운트가 0이 되면 후보 값을 현재 순회 중인 값으로 업데이트 한다.

---

답안 코드 1. Broute Force

Runtime: 2026 ms (5.12%)
Memory Usage: 15.5 MB (85.99%)

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        checked = []
        for i in range(len(nums)):
            if nums[i] in checked: # 이미 한 번 비교 기준이 되었던 수는 다시 탐색하지 않음
                continue
            
            cnt = 0
            for j in range(len(nums)):
                if nums[i] == nums[j]:
                    cnt = cnt + 1
                    checked.append(nums[i])
                if cnt > len(nums) // 2:
                    return nums[i]

 

답안 코드 2. 배열 정렬

Runtime: 345 ms (11.6%)
Memory Usage: 15.5 MB(85.99%)

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = 1
        nums.sort()
        
        if(len(nums) <= 1):
            return nums[0]
        for i in range(1, len(nums)):
            if cnt >= len(nums)//2:
                return nums[i]
            if nums[i-1] != nums[i]:
                cnt = 1
            else:
                cnt = cnt + 1

 

답안 코드 3. Boyer-Moore Voting Algorithm

Runtime: 180 ms (86.89%)
Memory Usage: 15.5 MB (85.99%)

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