LeetCode 169(Majority Element, Python)

1. 문제 링크

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

Majority Element - LeetCode

2. 문제 설명

• 크기가 n인 배열이 주어졌을 때, majority element를 반환
  • 여기서 majority element란, 배열 내에서 [n/2] 번 이상 존재한 element를 의미하며,
  • 배열 내에 majority element가 존재한다고 가정 ← 문제를 쉽게 만드는 요인
    • 예시1) [3,2,3] 이면 3이 배열에 2번(3/2보다 큰) 등장했으므로 3 반환
    • 예시2) [2,2,1,1,1,2,2] 에 2가 4번(7/2보다 큰) 등장했으므로 2 반환

3. 처음 풀이 

• history_dict에 element별 count를 센다.
  • 가장 큰 value를 가진 key가 당연히 majority element가 된다. 

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        history_dict = {} # hash table을 위한 빈 dict
        for i in nums: # for문을 돌리며 
            if i not in history_dict: # element가 처음 등장하면 1을 넣고 
                history_dict[i] = 1
            else:
                history_dict[i] += 1 # 이미 등장한 경우 1씩 더해주면서, key별 count를 센다
        
        return max(history_dict, key=history_dict.get) #그리고 dict의 가장 큰 value를 가진 key를 반환

• 생각보다 심플하게 풀렸고, runtime 92.57 beats, memory 96.26 beats로 결과도 잘나옴

4. 다른 풀이 

• 다른사람 풀이 중에 신박했던 풀이
  • 그냥 sort를 시킨 후에, k//2 번째  element를 불러오면, majority element가 된다.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        k = len(nums)
        return nums[k//2]

• 아래 풀이는 hash table 없이 list.count(element)를 비교해가면서 반환

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        unique = set(nums)
        for num in unique:
            if nums.count(num) > len(nums) / 2:
                return num

 

5. 배운 점 

• hash table을 잘 활용하기!