[코딩/LeetCode150-(5)] Majority Element (169)

 

본 글은 LeetCode Top Interview 150에 정리된 문제를 요약하고 이에 대한 개인적인 풀이를 포함하고있습니다.
본 포스팅 시리즈는 150 list의 순서를 따라서 게재됩니다. 풀이 언어는 python을 사용합니다.

 

 

 

난이도: EASY

키워드: Array, Hash Table

 

 

문제

문제 원문: https://leetcode.com/problems/majority-element/description/

 

크기가 n인 배열 nums가 주어졌을 때, 최빈도 (the majority) 원소를 반환해라. 최빈 (majority) 원소는 항상 존재하며, 이 원소의 수는 배열 길이의 절반을 넘는다.

 

예제

Input: nums = [3,2,3]
Output: 3

Input: nums = [2,2,1,1,1,2,2]
Output: 2

 

풀이 (Runtime: Beats 90.34%, Memory Beats 27.75  %)

counter를 사용하여 배열 내에 존재하는 원소들의 횟수를 얻은 후 (Hash Table을 사용한 counting) 이를 key값으로하여 정렬하였을 때 첫 번째 값을 반환. 하지만 이 풀이의 경우에는 memory의 사용이 O(n)이고 runtime complexity의 경우 hash map insertion의 복잡도를 따라 O(n)이다.

from collections import Counter

class Solution:
    def majorityElement(self, nums: List[int]) -> int:

        counter = Counter(nums)
        sorted_counter = sorted(counter.keys(), key= lambda x: counter[x], reverse=True)
        return sorted_counter[0]

 

이 외에도 sorting을 먼저 한 뒤에 indexing으로 찾는 방법등을 활용할 수 있을 것 같다.

 

 

🔎 Followup Question :
본 문제를 linear time O(n) 내에 O(1) space만 사용해서 풀 수 있는가? 

 

🔖  Boyer-Moore Voting 알고리즘을 사용한 방법

 

marjority에 해당하는 원소를 +1 , 아닌 그외의 원소를 -1이라고 했을 때, 이들 전체의 합은 양수를 만족해야한다. 따라서 배열을 순횧하면서 majority 값의 후보를 임의로 정하고 이들의 개수를 측정하는 방식으로 문제를 해결한다.

 

majority 값의 후보를 만나며 +1, 아니면 -1을 하는 변수 count가 주어진다고 하자. 본 알고리즘은 count = 0인 경우 후보 값을 업데이트하고, 해당 후보를 만나면 +1, 아니면 -1을 하며 0이 되는경우 후보 값을 업데이트한다. 이를 구현하면 다음과 같다.

 

class Solution:
    def majorityElement(self, nums: List[int]) -> int:

        count = 0

        for num in nums:

            if count == 0:
                candidate = num
            
            if num == candidate:
                count += 1
            else:
                count -= 1
        
        return candidate

 

📚 LeetCode 75 / Code Signal 풀이 보러가기