Leetcode - Majority Element

16 Oct 2024 in Algorithm

알고리즘 공부

Daily Leetcode

• 🔑 Naive Solution
• 🧱 Better Solution
• 💉 Best Solution (Boyer Moore Voting)

문제 링크

문제는 해석하면 과반수 이상 등장한 원소를 리턴하면 된다. 이번 문제는 총 3개의 솔루션이 제공된다.

🔑 Naive Solution

역시 처음에는 가장 원초적인 방법을 생각해보면 좋을 것 같다. 딕셔너리를 하나 만들어서 등장 횟수를 모두 저장해두고 그 등장 횟수를 정렬하면 좋을 거 같다. (사실 별로임)

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

        num_cnt = dict()

        for num in nums:
            num_cnt[num] = num_cnt.get(num, 0)+1

        num_cnt = sorted(num_cnt.items(), key=lambda x:-x[1])
        ret = num_cnt[0][0]

        return ret

코드는 말 그대로 구현해둔 것이고 분석을 해보자

• Time Complexity : O(nlogn)
• Space Complexity : O(n)

여기서 면접관이 Time / Space 중 하나를 줄여보라고 한다.

🧱 Better Solution

과반수에 집중해보자. 굳이 등장 횟수를 세서 정렬할 필요없이 데이터를 정렬하고 과반수는 어찌됐던 len(nums)//2 인덱스에 있지 않을까? 이를 나타내는 코드를 짜보자

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

        # Better Solution
        nums.sort()
        return nums[len(nums)//2]

• Time Complexity : O(nlogn)
• Space Complexity : O(1)

면접관이 시간복잡도도 선형으로 부탁한다.

💉 Best Solution (Boyer Moore Voting)

사실 이건 이 알고리즘을 알아야 풀 수 있다. 이 알고리즘의 특징으로는 과반수가 보장이 되어야 하며 우리가 알아낼 수 잇는 것은 과반수 이상의 숫자를 찾아내는 것이다.

이를 가장 잘 나타내는 그림이 있다.

코드로 보자.

count = 0
        ret = -1

        for num in nums:
            if count == 0: ret = num
            if ret == num: count += 1
            else: count -= 1
        return ret

• Time Complexity : O(n)
• Space Complexity : O(1)

가장 빠르며 추가적인 공간이 필요없는 풀이이다. 레벨은 easy이나 많은 것을 볼 수 있는 문제인 거 같다.