[Leetcode] 169. Majority Element

[Leetcode] 169. Majority Element

[Leetcode] 169. Majority Element

카테고리

📚 Algorithm

작성자

박용성

박용성

작성일

2024년 09월 12일

태그

Python

Leetcode

Slug

Leetcode-169

🖥️ 시작하며

Given an array nums of size n, return the majority element.

배열에서 과반수 요소를 찾으면 된다. 과반수 요소가 항상 존재한다고 가정하므로 문제의 난이도가 쉬워진다.

⚙️ Python


from typing import List


class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return max(nums, key=nums.count)

파이썬의 경우는 매우 쉽다. 물론 시간 복잡도가 O(n²) 이지만 간단하게 풀린다. max 함수의 key로 함수가 들어갈 수 있다는 걸 아는 것이 중요하다.

💡 더 좋은 아이디어


class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 1
        major = nums[0]
        length = len(nums)

        for i in range(1, length):
            if count == 0:
                count += 1
                major = nums[i]
            elif nums[i] == major:
                count += 1
            else:
                count -= 1

        return major

시간 복잡도가 O(n) 인 좋은 코드다. 이 코드는 과반수 원소가 절반 이상 등장한다는 특성을 이용하여, 마지막까지 남는 원소가 실제로 과반수 원소임을 보장한다.

📌 소감

파이썬은 메소드를 많이 아는 게 중요한 것 같다.

댓글